Math Homework

Time limit1sMemory limit1024 MB

Summary

Construct a sequence of N integers in [1, 10^9] so that the GCD of each given subarray equals a given value at most 16, or report impossibility.

Level: Hard8 of 10
Topics: Number theory, Math, Segment tree, Greedy
Solved: No attempts yet

Problem

Your math teacher has given you an assignment involving coming up with a sequence of $N$ integers $A_1, \ldots, A_N$ , such that $1 \le A_i \le 1\,000\,000\,000$ for each $i$ .

The sequence $A$ must also satisfy $M$ requirements, with the $i$ th one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence $A_{X_i}, \ldots, A_{Y_i}$ ( $1 \le X_i \le Y_i \le N$ ) must be equal to $Z_i$ . The GCD of a sequence of integers is the largest integer $d$ such that all the numbers in the sequence are divisible by $d$ .

Find any valid sequence $A$ consistent with all of these requirements, or determine that no such sequence exists.

Input

The first line contains two space-separated integers, $N$ and $M$ .

The next $M$ lines each contain three space-separated integers, $X_i$ , $Y_i$ , and $Z_i$ ( $1 \le i \le M$ ).

Output

If no such sequence exists, output the string Impossible on one line. Otherwise, on one line, output $N$ space-separated integers, forming the sequence $A_1, \ldots, A_N$ . If there are multiple possible valid sequences, any valid sequence will be accepted.

Constraints

$1 \le N \le 150\,000$
$1 \le M \le 150\,000$
$1 \le Z_i \le 16$ for each $i$

Examples2

Example 1
Input
```
2 2
1 2 2
2 2 6
```
Expected output
```
4 6
```
Example 2
Input
```
2 2
1 2 2
2 2 5
```
Expected output
```
Impossible
```