NSD

Easy

Execution time limit is 1 second

Runtime memory usage limit is 256 megabytes

Find an array $a$ consisting of $n$ positive integers (also known as natural numbers) that meets $m$ specified constraints:

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

Here, $g cd$ denotes the greatest common divisor.

Input

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

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

Output

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

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

Examples

Input #1

Answer #1

Input #2

Answer #2

Scoring

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

Submissions 110

Acceptance rate 20%