P9027 [CCC 2021 S5] Math Homework

构造一个长度为 $N$ 的整数序列 $A$，使得： 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$。 或者报告无解。

第一行，$N,M$。 接下来 $M$ 行，每行有 $X_i,Y_i,Z_i$，描述一个限制 2.

一行，序列 $A$，或者 `Impossible`。

$$1\leq N\leq 150000,1\leq M\leq 150000,1\leq Z_i\leq 16$$ 译自 [CCC2021 S5](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。 spj 在附件里，发现锅了请联系[我](/user/90693)。