НСД

Знайдіть будь-який масив $a$ з $n$ цілих додатних чисел (їх іноді також називають натуральними), для якого виконуються $m$ обмежень:

$\gcd$ — найбільший спільний дільник.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ($1\le n,m\le 150000$).

Кожен з наступних $m$ рядків містить по три цілі числа $l_i$, $r_i$, $x_i$ ($1\le l_i\le r_i\le n$, $1\le x_i\le 16$).

Вихідні дані

Якщо такий масив існує, то виведіть $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$).

Якщо такого масиву немає, то виведіть $-1$.

Приклади

Оцінювання

1. ($21$ бал): $n,m\le 2000$; $x_i\le 2$;

2. ($30$ балів): $n,m\le 2000$;

3. ($49$ балів): без додаткових обмежень.