Problem Description

Construct an integer sequence $A$ of length $N$ such that:

1. $\forall i=1,2,\cdots,N, 1\leq A_i\leq 10^9$.
2. $\forall i=1,2,\cdots,M, \gcd(A_{X_i},A_{X_i+1},\cdots,A_{Y_i})=Z_i$.

Or report that there is no solution.

Input Format

The first line contains $N, M$.

The next $M$ lines each contain $X_i, Y_i, Z_i$, describing constraint 2.

Output Format

Output one line: the sequence $A$, or Impossible.

2 2
1 2 2
2 2 6

4 6

2 2
1 2 2
2 2 5

Impossible

Hint

$$1\leq N\leq 150000, 1\leq M\leq 150000, 1\leq Z_i\leq 16.$$

Translated from CCC2021 S5.

The special judge (spj) is in the attachment. If you find any issues, please contact me.

Translated by ChatGPT 5