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$≤1000000000 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$_{Xi}$,…,A$_{Yi}$ (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.