## CCC '21 S5 - Math Homework

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 512M

Problem types

Note: This problem originated from the 2021 CCC Senior contest. CBOJ is in no way affiliated with the CEMC.

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.

#### Input Specification

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)$$. The following table shows how the available $$15$$ marks are distributed.

Subtask $$N$$ $$M$$ $$Z_i$$
$$3$$ marks $$1 \le N \le 2\,000$$ $$1 \le M \le 2\,000$$ $$1 \le Z_i \le 2$$ for each $$i$$
$$4$$ marks $$1 \le N \le 2\,000$$ $$1 \le M \le 2\,000$$ $$1 \le Z_i \le 16$$ for each $$i$$
$$8$$ marks $$1 \le N \le 150\,000$$ $$1 \le M \le 150\,000$$ $$1 \le Z_i \le 16$$ for each $$i$$

#### Output Specification

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.

#### Sample Input 1

2 2
1 2 2
2 2 6

#### Output for Sample Input 1

4 6

#### Explanation of Output for Sample Input 1

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.

Sample Input 2

2 2
1 2 2
2 2 5

#### Output for Sample Input 2

Impossible

#### Explanation of Output for Sample Input 2

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