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

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

0.2 seconds
256 megabytes
Medium

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

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

Input

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

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading