Description

There are n children in Johnny Johnny' s family.

And number i child wants to have a_i units of sugar.

But their PaPa don't want them eat too much sugar. Therefore he will randomly choose some children and only give them the great common divisor of a_i. 

 

For example, if there're n=5 children and a_i = { 1, 4, 6, 7, 18 }.

Suppose PaPa choose the children numbered 2,3,5.

Then all children will only get  gcd(a₂, a₃, a₅) = gcd(4,6,18) = 2 unit of sugar.

 

Now Johnny wants to know what's the maximum amount of sugar they can get.(PaPa will at least choose two child) 

If you can help him, he will laugh at you for you don't have any sugar " Ha Ha Ha!!! "

 

To calculate great common divisor, you can use the method 輾轉相除法(https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)

Input

input contains two lines.

First line only contains one integer n ( 2 <= n <=  1000)

Second line contain n integers a₁ ~ a_n ( 1<= a_i <= 1000 )

Output

output contains only one integer the maximum amount of sugar they can get.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Johnny just got a lot of sugar from his PaPa!

However, Johnny is too excited that he accidently fall and all of the sugar just fall onto the ground. 

PaPa is angry, and asked Johnny to clean the room up and take all his sugar away. 

After Johnny's begging, PaPa thought of a problem. If Johnny could solve it, PaPa may just forgive him.

The sugar now seperated on the ground. The ground is a 2D coordinate with n * n slots, each slot has several pieces of sugar. PaPa will give Johnny the number of pieces of sugar in each slot. Johnny needs to answer the maximum number of every row and the minimum number of every column, otherwise, he will be punished!

Johnny is a bad boy, he command you to help him, and if you do it well, he will not give you any sugar, but you'll receive an AC.

Input

The first line contains only one integer that indicates the number n.

The next n lines, each line contains n non-negitive integers, PaPa will give you the number of pieces of sugar in each slot.

1 <= n <=1000, each piece of sugar will not excceed 50000. 

Output

The first line, output the maximum number of each row. There should be n numbers.

The second line, output the minimum number of each column. There should be n numbers, too.

There should be a space next to each number except the last number, which means there should be no space at the end of each line.

Remember to output a '\n' at the end of the output. 

Sample Input  Download

Sample Output  Download

Tags

Discuss