НСД

Найдите массив $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$ баллов): без дополнительных ограничений.