Юний художник

Limits: 1 sec., 256 MiB

Юний художник Зеник має \(n\) послідовно розташованих білих комірок, пронумерованих від 1 до \(n\) зліва направо, які можна фарбувати.

Він виконує \(m\) фарбувань такого вигляду: \((l,\) \(r,\) \(c)\) — зафарбувати усі комірки від \(l\) до \(r\) включно в колір \(c\). Кожна комірка пофарбована тільки в останній колір, яким фарбувалася відовідна комірка.

Вам потрібно відновити кінцеву картину, тобто визначити кольори усіх комірок після виконання всіх запитів.

Input

У першому рядку задано два цілих числа \(n\) і \(m\) — кількість комірок та кількість фарбувань.

У наступних \(m\) рядках задано по 3 цілих числа \(l\), \(r\) і \(c\) — відповідне фарбування.

Output

У єдиному рядку виведіть \(n\) цілих чисел через пробіл — кольори комірок після усіх фарбувань.

Вважайте, що білий колір — це 0.

Constraints

\(1 \le n, m, c \le 10^5\),

\(1 \le l \le r \le n\).

Samples