|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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.
2 2 1 2 2 2 2 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 1 2 2 2 2 5
There exists no sequence [A1, A2] such that the GCD of [A1, A2] is 2 and the GCD of [A2] is 5.