Math Homework

문제

Your math teacher has given you an assignment involving coming up with a sequence of N integers A₁, . . . , 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_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.

입력

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

출력

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