Nastya and Decryption#10253
Nastya recently joined a decryption club. After breezing through the initial tasks, she was presented with a more challenging cipher. This cipher involves two arrays of positive integers, with lengths and , respectively. These arrays are encrypted into a table of size n \times m, where each element v_{ij} represents the greatest common divisor (GCD) of the numbers a_i and b_j from the arrays.
Nastya has been given the table and needs to determine any two original arrays of positive integers, where each number is no greater than 10^9, that could have been encrypted to produce this table. Your task is to assist her in finding these arrays.
The first line contains two integers and (1 \leq n, m \leq 500) — the lengths of the two arrays.
The following lines each contain integers v_{i1}, v_{i2}, \ldots, v_{im} (1 \leq v_{ij} \leq 10^9) — the elements of the table .
The first line should output integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the elements of the first array.
The second line should output integers b_1, b_2, \ldots, b_m (1 \leq b_i \leq 10^9) — the elements of the second array.
If there are multiple valid solutions, you may output any of them.
If no solution is possible, output on a single line.
Example 1
Example 2