#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
long long a[100000];
long long gcd(long long a,long long b)
{
	return b?gcd(b,a%b):a;
}

int cmp(const long long &a,const long long &b)
{
	if (a%2==0 && b%2==1) return 1;
	else if (a%2==1 && b%2==0) return 0;
	else return a<b;
}
int main()
{
	int N,n;
	while(1)
	{
		long long x,y,z,tmp,r1,r2,d2,m,p,q;
		scanf("%d",&n);
		if (n==0) break;
		N=(n+1)*n/2;
		for (int i=1;i<=N;i++) scanf("%lld",a+i);

		sort(a+1,a+N+1,cmp);
		x=a[n+1]; y=a[1];	z=a[2];

		tmp=gcd(y,z);	r1=y/tmp;	r2=z/tmp;
		d2=x/r1/r2;

		p=1;q=(1<<31)-1;
		while (p<=q)
		{
			m=(p+q)>>1;
			if (m*m==d2) break;
			else if (m*m<d2) p=m+1;
			else q=m-1;
		}
		tmp/=m;

		printf("%lld\n",tmp);
		for (int i=1;i<=n;i++)
			{
				if (i<n) printf("%lld ",a[i]/tmp);
				else printf("%lld\n",a[i]/tmp);
			}
	}
	return 0;
}
### Prompt

Generate a Cpp solution to the following problem:

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

### Response

```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
long long a[100000];
long long gcd(long long a,long long b)
{
	return b?gcd(b,a%b):a;
}

int cmp(const long long &a,const long long &b)
{
	if (a%2==0 && b%2==1) return 1;
	else if (a%2==1 && b%2==0) return 0;
	else return a<b;
}
int main()
{
	int N,n;
	while(1)
	{
		long long x,y,z,tmp,r1,r2,d2,m,p,q;
		scanf("%d",&n);
		if (n==0) break;
		N=(n+1)*n/2;
		for (int i=1;i<=N;i++) scanf("%lld",a+i);

		sort(a+1,a+N+1,cmp);
		x=a[n+1]; y=a[1];	z=a[2];

		tmp=gcd(y,z);	r1=y/tmp;	r2=z/tmp;
		d2=x/r1/r2;

		p=1;q=(1<<31)-1;
		while (p<=q)
		{
			m=(p+q)>>1;
			if (m*m==d2) break;
			else if (m*m<d2) p=m+1;
			else q=m-1;
		}
		tmp/=m;

		printf("%lld\n",tmp);
		for (int i=1;i<=n;i++)
			{
				if (i<n) printf("%lld ",a[i]/tmp);
				else printf("%lld\n",a[i]/tmp);
			}
	}
	return 0;
}
```