| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 90 | 31 | 30 | 38.462% |
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
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 1 2 2 2 2 5
Impossible
There exists no sequence [A1, A2] such that the GCD of [A1, A2] is 2 and the GCD of [A2] is 5.