## CCC '21 S5 - Math Homework

View as PDF

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types
##### Canadian Computing Competition: 2021 Stage 1, Senior #5

Your math teacher has given you an assignment involving coming up with a sequence of integers , such that for each .

The sequence must also satisfy requirements, with the one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence must be equal to . Note that the GCD of a sequence of integers is the largest integer such that all the numbers in the sequence are divisible by .

Find any valid sequence consistent with all of these requirements, or determine that no such sequence exists.

#### Input Specification

The first line contains two space-separated integers, and . The next lines each contain three space-separated integers, , , and .

The following table shows how the available marks are distributed.

marks for each
marks for each
marks for each

Note: an additional test case worth 1 point was added to prevent unintended solutions from passing.

#### Output Specification

If no such sequence exists, output the string Impossible on one line. Otherwise, on one line, output space-separated integers, forming the sequence . 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 and , the GCD of is and the GCD of is , 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 such that the GCD of is and the GCD of is .