Знайдіть будь-який масив $a$ з $n$ цілих додатних чисел (їх іноді також називають натуральними), для якого виконуються $m$ обмежень: $$\gcd(a_{l_i}, a_{l_i+1}, \dots, a_{r_i})=x_i$$ $\gcd$~--- найбільший спільний дільник. \InputFile Перший рядок містить два цілі числа $n$ та $m$ ($1 \leq n, m \leq 150\,000$). Кожен з наступних $m$ рядків містить по три цілі числа $l_i$, $r_i$, $x_i$ ($1 \leq l_i \leq r_i \leq n$, $1 \leq x_i \leq 16$). \OutputFile Якщо такий масив існує, то виведіть $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$). Якщо такого масиву немає, то виведіть $-1$. \Scoring \begin{enumerate} \item ($21$ бал): $n, m \leq 2\,000$; $x_i \leq 2$; \item ($30$ балів): $n, m \leq 2\,000$; \item ($49$ балів): без додаткових обмежень. \end{enumerate}