수학 숙제

수학 선생님이 $N$개의 정수 $A_1, \ldots, A_N$으로 이루어진 수열을 만드는 숙제를 내주셨다. 각 $i$에 대해 $1 \le A_i \le 1\,000\,000\,000$을 만족해야 한다.

수열 $A$는 $M$개의 조건도 만족해야 한다. $i$번째 조건은 연속한 부분수열 $A_{X_i}, \ldots, A_{Y_i}$ ($1 \le X_i \le Y_i \le N$)의 최대공약수가 $Z_i$와 같아야 한다는 것이다. 수열의 최대공약수는 수열의 모든 수를 나누는 가장 큰 정수 $d$이다.

모든 조건을 만족하는 수열 $A$를 아무거나 하나 찾거나, 그러한 수열이 존재하지 않는다고 판별하라.

첫째 줄에 공백으로 구분된 두 정수 $N$과 $M$이 주어진다.

다음 $M$개의 줄에 각각 공백으로 구분된 세 정수 $X_i$, $Y_i$, $Z_i$가 주어진다 ($1 \le i \le M$).

그러한 수열이 존재하지 않으면 한 줄에 문자열 Impossible을 출력한다. 그렇지 않으면 한 줄에 공백으로 구분된 $N$개의 정수 $A_1, \ldots, A_N$을 출력한다. 가능한 수열이 여러 개라면 아무거나 출력해도 된다.

• $1 \le N \le 150\,000$
• $1 \le M \le 150\,000$
• 각 $i$에 대해 $1 \le Z_i \le 16$