p00654 Squid Multiplication_17037
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//Squid Multiplication
public class Main{

	long gcd(long a, long b){
		return b==0?a:gcd(b, a%b);
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			List<Long> even = new ArrayList<Long>(), odd = new ArrayList<Long>(), list = new ArrayList<Long>();
			for(int i=0;i<n*(n+1)/2;i++){
				long x = sc.nextLong();
				list.add(x);
				if(x%2==0)even.add(x);
				else odd.add(x);
			}
			Collections.sort(list);
			boolean con = true;
			for(int i=0;i<even.size()&&con;i++)for(int j=i+1;j<even.size()&&con;j++){
				long bi = even.get(i), bj = even.get(j), bk = odd.get(0);
				long g = gcd(bi, bk);
				bi/=g; bk/=g;
				g = gcd(bj, bk);
				bj/=g; bk/=g;
				double r = Math.sqrt(bi*bj/bk);
				long a0 = (long)r;
//				System.out.println("GCD:"+a0);
				if(a0==0)continue;
				long[] a = new long[n];
				boolean f = true;
				List<Long> l = new ArrayList<Long>();
				for(int x=0;x<n;x++){
					long y = even.get(x);
					if(y%a0!=0){
						f = false; break;
					}
					a[x]=even.get(x)/a0;
					l.add(a0*a[x]);
				}
				if(!f)continue;
//				if(a0==18){
//					System.out.println("*************************************");
//					Arrays.sort(a);
//					for(long x:a)System.out.println(x);
//							System.out.println("*************************************");
//				}
				for(int x=0;x<n;x++)for(int y=x+1;y<n;y++)l.add(a[x]*a[y]);
				Collections.sort(l);
				boolean ok = true;
				for(int x=0;x<l.size();x++){
//					if(a0==18){
//						System.out.println("L:"+l.get(x)+" LIST:"+list.get(x));
//					}
					long A = l.get(x), B = list.get(x);
					if(A!=B){
						ok = false; break;
					}
				}
				if(ok){
					Arrays.sort(a);
					System.out.println(a0);
					con = false;
					for(int x=0;x<n;x++)System.out.print(a[x]+(x==n-1?"\n":" "));
				}
			}
		}

	}

	public static void main(String[] args) {
		new Main().run();
	}
}