e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

НСД

Знайдіть будь-який масив $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}
Time limit 1 second
Memory limit 256 MiB
Input example #1
2 2
1 2 2
2 2 6
Output example #1
2 6
Input example #2
2 2
1 2 2
2 2 5
Output example #2
-1
Author Anton Tsypko