Canadian Computing Competition: 2021 Stage 1, Senior #5

Your math teacher has given you an assignment involving coming up with a sequence of \(N\) integers \(A_1, \dots, 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^\text{th}\) one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence \(A_{X_i}, \dots, A_{Y_i}\) \((1 \le X_i \le Y_i \le N)\) must be equal to \(Z_i\) . Note that 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 Specification

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)\) .

The following table shows how the available \(15\) marks are distributed.

Note: an additional test case worth 1 point was added to prevent unintended solutions from passing.

Output Specification

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, \dots, A_N\) . If there are multiple possible valid sequences, any valid sequence will be accepted.

Sample Input 1

2 2
1 2 2
2 2 6

Output for Sample Input 1

4 6

Explanation of Output for Sample Input 1

If \(A_1 = 4\) and \(A_2 = 6\) , the GCD of \([A_1, A_2]\) is \(2\) and the GCD of \([A_2]\) is \(6\) , as required. Please note that other outputs would also be accepted.

Sample Input 2

2 2
1 2 2
2 2 5

Output for Sample Input 2

Impossible

Explanation of Output for Sample Input 2

There exists no sequence \([A_1, A_2]\) such that the GCD of \([A_1, A_2]\) is \(2\) and the GCD of \([A_2]\) is \(5\) .