Дистанционный практикум по программированию

Schoolboy Vasya is toying with numbers. He chooses n distinct positive integers a₁, a₂, …, a_n in ascending order and calculates the greatest common denominators (GCD) for all pairs <a_i, a_j> with i < j, writing down the results in a table. For example, numbers 1, 2, 3, 4, 5, 6, 7, 8 will produce the following GCD table:

                            1: 1, 1, 1, 1, 1, 1, 1

                            2: 1, 2, 1, 2, 1, 2

                            3: 1, 1, 3, 1, 1

                            4: 1, 2, 1, 4

                            5, 1, 1, 1

                            6: 1, 2

                            7: 1

                            8:

Obviously, several sequences can produce the same GCD table, thus in general it is impossible to restore the exact original sequence using only the GCD table. Write a program that, given the GCD table, will restore a possible initial sequence a₁, a₂, …, a_n. If several such sequences exist then any of them will be considered as a correct answer.

 

Limitations

1 <= n <= 100; 1 <= a_i <= 10⁹; 1 <= GCD(a_i , a_j) <= 10⁴.

 

Input

The first line contains an integer n, the number of integers in the sequence. The following n–1 lines describe the rows of the GCD table for a₁, a₂, …, a_n–1, respectively. The line for a_i contains n–i integers separated by spaces: GCD(a_i, a_i+1),  GCD(a_i, a_i+2), …, GCD(a_i, a_n). You can safely assume that the input data is based on some real sequence a₁, a₂, a₃, …, a_n, which means that a solution always exists.

 

Output

The output file should contain n space-delimited integers: possible initial numbers a₁, a₂, …, a_n, respectively.

 

Example

Input	Output
4 4 4 2 4 2 6	4 8 12 18

 

Input	Output
4 2 2 2 2 2 2	2 6 8 10

 

 

All Rybinsk-2012 problems (in PDF)