시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 2 2 2 100.000%

문제

Your math teacher has given you an assignment involving coming up with a sequence of N integers A1, . . . , AN, such that 1 ≤ Ai ≤ 1 000 000 000 for each i.

The sequence A must also satisfy M requirements, with the ith one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence AXi , . . . , AYi (1 ≤ Xi ≤ Yi ≤ N) must be equal to Zi. 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, Xi, Yi, and Zi (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 A1, . . . , AN. If there are multiple possible valid sequences, any valid sequence will be accepted.

제한

  • 1 ≤ N ≤ 150 000
  • 1 ≤ M ≤ 150 000
  • 1 ≤ Zi ≤ 16 for each i

예제 입력 1

2 2
1 2 2
2 2 6

예제 출력 1

4 6

If A1 = 4 and A2 = 6, the GCD of [A1, A2] is 2 and the GCD of [A2] is 6, as required. Please note that other outputs would also be accepted.

예제 입력 2

2 2
1 2 2
2 2 5

예제 출력 2

Impossible

There exists no sequence [A1, A2] such that the GCD of [A1, A2] is 2 and the GCD of [A2] is 5.