CCC '21 S5 - Math Homework

Canadian Computing Competition: 2021 Stage 1, Senior #5

Your math teacher has given you an assignment involving coming up with a sequence of $N$ integers $A_1, \ldots, A_N$, such that $1 \le A_i \le 1\,000\,000\,000$ for each $i$.

The sequence $A$ must also satisfy $M$ requirements, with the $i^\text{th}$ one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence $A_{X_i}, \ldots, A_{Y_i}$ ($1 \le X_i \le Y_i \le 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 \le i \le M$).

The following table shows how the available $15$ marks are distributed.

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

Sample Input 1

Sample Output 1

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

Sample Output 2

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