NSD

Asan

Zaman limiti 1 saniyə-dir

Yaddaş məhdudiyyəti 256 meqabayt

Tapşırıq: $n$ ədəd tam müsbət ədədlərdən ibarət $a$ massivini tapın (bəzən bunlara təbii ədədlər də deyilir), hansı ki, $m$ məhdudiyyətlərini təmin edir:

g cd (a_{l_{i}}, a_{l_{i} + 1}, \dots, a_{r_{i}}) = x_{i}

Burada $g cd$ ən böyük ortaq böləndir.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $m$ ( $1 \leq n, m \leq 150000$ ) ehtiva edir.

Növbəti $m$ sətirin hər biri üç tam ədəd $l_{i}$ , $r_{i}$ , $x_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ , $1 \leq x_{i} \leq 16$ ) ehtiva edir.

Çıxış verilənləri

Əgər belə bir massiv mövcuddursa, $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 1 0^{9}$ ) çıxarın.

Əgər belə bir massiv mövcud deyilsə, $- 1$ çıxarın.

Nümunələr

Giriş #1

Çıxış #1

Giriş #2

Çıxış #2

Qiymətləndirmə

( $21$ bal): $n, m \leq 2000$ ; $x_{i} \leq 2$ ;
( $30$ bal): $n, m \leq 2000$ ;
( $49$ bal): əlavə məhdudiyyətlərsiz.

Təqdimatlar 118

Qəbul dərəcəsi 19%