Знайдіть будь-який масив a з n цілих додатних чисел (їх іноді також називають натуральними), для якого виконуються m обмежень:
gcd — найбільший спільний дільник.
Перший рядок містить два цілі числа n та m (1≤n,m≤150000).
Кожен з наступних m рядків містить по три цілі числа li, ri, xi (1≤li≤ri≤n, 1≤xi≤16).
Якщо такий масив існує, то виведіть n цілих чисел a1,a2,…,an (1≤ai≤109).
Якщо такого масиву немає, то виведіть −1.
(21 бал): n,m≤2000; xi≤2;
(30 балів): n,m≤2000;
(49 балів): без додаткових обмежень.