Quest#5241
During the LKS-2017 quest, the instructors presented the students with a challenge. Each of the instructors had a number in mind. A student could approach two instructors and inquire about their numbers. In response, the instructors would reveal the greatest common divisor (GCD) of the numbers they had thought of.
The students asked about pairs of instructors. Your task is to help the students deduce the numbers that the instructors were thinking of.
The first line of the input contains two integers: and (2 \le n \le 10, 0 \le m \le 45). The following lines each contain three integers: , , and . This triplet indicates that the greatest common divisor of the numbers thought of by the -th and -th instructors is (1 \le d \le 100). For each pair of and , there is at most one provided. The instructors are numbered from to .
If there is no possible solution, output the word impossible. Otherwise, output integers representing the numbers thought of by the instructors. Each number must be positive and not exceed 10^{18}. If multiple solutions exist, you may output any one of them.
Example 1