Note: This problem originated from the 2021 CCC Senior contest. CBOJ is in no way affiliated with the CEMC.

Your math teacher has given you an assignment involving coming up with a sequence of \(N\) integers \(A_1, . . . , A_N\) , such that \(1 ≤ A_i ≤ 1 000 000 000\) for each \(i\).

The sequence \(A\) must also satisfy \(M\) requirements, with the \(i\) th one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence \(A_{X_i}\) \(, . . . , A_{Y_i}\) \((1 ≤ X_i ≤ Y_i ≤ 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 ≤ i ≤ M)\). The following table shows how the available \(15\) marks are distributed.

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