Відновлення масивів

У голови журі олімпіади було декілька класних числових масивів, які він збирався використати для однієї цікавої задачі. Ці масиви йому дуже подобалися, але він їх загубив $-$ просто випадково видалив файли, у яких ці масиви були записані...

Але не все так погано! Відомо, що голова журі робив запити до втрачених масивів. Результати цих запитів мають такий вигляд: $[f_i$ $s_i$ $X_i]$, це означає, що мінімум із елементів з індексами $f_i$ та $s_i$ дорівнює $X_i$. Напишіть програму, яка за відомими запитами відновить втрачені масиви!

Input

У першому рядку вхідних даних записані ціле число $N$ $-$ кількість елементів у втраченому масиві ($1\le N\le 100000$) та ціле число $M$ $-$ кількість запитів ($1\le M\le 100000$). У кожному з наступних $M$ рядків описуються запити, які задаються трьома числами: $f_i$, $s_i$, $X_i$ ($1\le f_i,s_i\le N$, $1\le X_i\le 10^9$).

Output

Виведіть втрачений масив з $N$ натуральних чисел. Усі елементи цього масиву не повинні перевищувати $10^9$. Гарантується, що такий масив існує. Якщо є декілька масивів, які задовольняють усім запитам, то виведіть будь-який.

Examples