Problem Background

Lianlian is a lovely girl who has recently become obsessed with solving math problems.

Problem Description

Lianlian is currently working on a very simple problem: there are \( k \) \((2 \leq k \leq 4)\) numbers, and she doesn't know what they are, but she knows their pairwise greatest common divisors (GCD) and least common multiples (LCM).

Following the usual routine, Lianlian really wants to reconstruct those \( k \) numbers. However, she needs to pretend she can't solve it, so she hands the problem over to you. If you successfully solve this problem, Lianlian will be cheering wildly behind you...

Input Format

The first line contains two integers \( T \) and \( k \).

The next \( 2T \) lines contain \( T \) sets of data, each set consisting of two lines:

• The first line contains \(\frac{k(k-1)}{2}\) integers, representing the pairwise GCDs of the \( k \) unknown numbers, in random order.
• The second line contains \(\frac{k(k-1)}{2}\) integers, representing the pairwise LCMs of the \( k \) unknown numbers, in random order.

Output Format

Output \( T \) lines, each containing \( k \) space-separated numbers, representing any one set of answers that match the corresponding data.

Sample Input and Output

Sample Input #1

1 3
4 6 2
48 144 36

Sample Output #1

16 12 18

Sample Input #2

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 

Sample Output #2

16 12 18 4
7 8 9 10

Notes

In odd-numbered test cases, the first line (GCD line) data are all \( 1 \)

Guaranteed that the data has a solution, \( T \leq 5 \)

The scoring is based on the correct proportion of each set, but TLE, RE, etc., will result in no output and zero points.

见题面 Input 部分

见题面 Output 部分