GCD — Eolymp

Input

The first line contains two integers, $n$ and $m$ ( $1 \leq n, m \leq 150000$ 1 \leq n, m \leq 150\,000).

Each of the following $m$ lines contains three integers: $l_{i}$ l_i, $r_{i}$ r_i, and $x_{i}$ x_i ( $1 \leq l_{i} \leq r_{i} \leq n$ 1 \leq l_i \leq r_i \leq n, $1 \leq x_{i} \leq 16$ 1 \leq x_i \leq 16).

Output

If such an array exists, output $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \leq a_i \leq 10^9).

If no such array can be constructed, output $- 1$ .

Examples

Example 1

Loading

Example 2

Loading

Scoring

( $21$ points): $n, m \leq 2000$ n, m \leq 2\,000; $x_{i} \leq 2$ x_i \leq 2;
( $30$ points): $n, m \leq 2000$ n, m \leq 2\,000;
( $49$ points): no additional constraints.