Problem S5: Math Homework

Problem DescriptionCopy Anchor Link

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$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 SpecificationCopy Anchor Link

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 SpecificationCopy Anchor Link

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 1Copy Anchor Link

2 2
1 2 2
2 2 6

Output for Sample Input 1Copy Anchor Link

4 6

Explanation of Output for Sample Input 1Copy Anchor Link

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 2Copy Anchor Link

2 2
1 2 2
2 2 5

Output for Sample Input 2Copy Anchor Link

Impossible

Explanation of Output for Sample Input 2Copy Anchor Link

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