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.

The first line contains two space-separated integers, $N,M\ (1\leq N \leq 150,000,\ 1 \leq M \leq 150,000)$. 

The next $M$ lines each contain three space-separated integers, $X_i, Y_i, Z_i\ (1\leq Z_i \leq 16,\ 1≤i≤M)$.

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.

4 6

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.

Impossible

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.