P9027 [CCC 2021 S5] Math Homework

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.

The first line contains $N, M$. The next $M$ lines each contain $X_i, Y_i, Z_i$, describing constraint 2.

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

$$1\leq N\leq 150000, 1\leq M\leq 150000, 1\leq Z_i\leq 16.$$ Translated from [CCC2021 S5](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf). The special judge (spj) is in the attachment. If you find any issues, please contact [me](/user/90693). Translated by ChatGPT 5