Description

The problem Lianlian is working on now is very simple: there are $k \space (2\leq k\leq 4)$ numbers. Lianlian does not know what they are, but she knows the pairwise greatest common divisors and least common multiples of these numbers.

As usual, Lianlian really wants to reconstruct those $k$ numbers, but now she needs to pretend she cannot do it, so she hands the problem to you. If you solve it successfully, Lianlian will cheer for you like crazy behind your back.

Input Format

The first line contains two integers $T$ and $k$.

The next $2T$ lines contain $T$ test cases, and each test case consists of two lines.

The first line contains $\frac{k(k-1)}2$ integers, representing the pairwise greatest common divisors of the $k$ unknown numbers, in arbitrary order.

The second line contains $\frac{k(k-1)}2$ integers, representing the pairwise least common multiples of the $k$ unknown numbers, in arbitrary order.

Output Format

Output $T$ lines. Each line contains $k$ numbers separated by spaces, representing any one set of answers that matches the given data.

1 3
4 6 2
48 144 36

16 12 18

2 4
4 2 4 6 4 2
48 144 16 36 12 36
1 1 1 1 2 1 
56 63 70 72 40 90 

16 12 18 4
7 8 9 10

Hint

It is guaranteed that for odd-numbered test points, the first line (the gcd line) is all $1$.

It is guaranteed that the testdata has a solution, and $T\leq 5$.

The SPJ scores according to the correct ratio within each test case, but if TLE, RE, etc. causes no output, you will get zero points.

Translated by ChatGPT 5