p00654 Squid Multiplication_17035
Problem H: Squid Multiplication

Squid Eiko loves mathematics. Especially she loves to think about integer. One day, Eiko found a math problem from a website.

"A sequence b ={ai + aj | i < j } is generated from a sequence a ={a0 , ... , an | ai is even if i is 0, otherwise ai is odd}. Given the sequence b , find the sequence a ."

This problem is easy for Eiko and she feels boring. So, she made a new problem by modifying this problem .

"A sequence b ={ai *aj | i < j } is generated from a sequence a ={ a0, ... , an | ai is even if  i  is 0, otherwise ai is odd}. Given the sequence b , find the sequence a ."

Your task is to solve the problem made by Eiko.



Input

Input consists of multiple datasets.
Each dataset is given by following formats.


n
b0 b1 ... bn*(n+1)/2-1


n is the number of odd integers in the sequence a. The range of n is 2 ≤ n ≤ 250. bi is separated by a space. Each bi is 1 ≤ bi ≤ 263-1. The end of the input consists of a single 0.

Output

For each dataset, you should output two lines. First line contains a0, an even number in the sequence a. The second line contains n odd elements separated by a space. The odd elements are sorted by increasing order. You can assume that the result is greater than or equal to 1 and less than or equal to 231-1.

Example

Input

3
6 10 14 15 21 35
2
30 42 35
0


Output

2
3 5 7
6
5 7
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

#define MAXX 65555

unsigned long long gcd(const unsigned long long &a,const unsigned long long &b)
{
    return b?gcd(b,a%b):a;
}

unsigned long long n,i,j,k,m;
unsigned long long num[MAXX],g;
std::vector<unsigned long long>ev,od;

int main()
{
    ev.reserve(MAXX);
    od.reserve(MAXX);
    while(scanf("%llu",&n),n)
    {
        m=n*(n+1)/2;
        ev.resize(0);
        od.resize(0);
        for(i=0;i<m;++i)
        {
            scanf("%llu",num+i);
            if(!(num[i]&1))
                ev.push_back(num[i]);
            else
                od.push_back(num[i]);
        }
        std::sort(ev.begin(),ev.end());
        std::sort(od.begin(),od.end());
        g=ev[0];
        for(i=1;i<ev.size();++i)
            g=gcd(g,ev[i]);
        k=od[0]/(ev[0]/g)/(ev[1]/g);
        g/=sqrt(k);
        printf("%llu\n%llu",g,ev[0]/g);
        for(i=1;i<ev.size();++i)
            printf(" %llu",ev[i]/g);
        puts("");
    }
    return 0;
}