Your task is to find the lexicographically lowest -gcd equivalent of a given sequence of positive integers . Two sequences (that are permutations of each other) and are considered -gcd equivalent if for every set of distinct indices from to , the greatest common divisor (gcd) of the elements in these positions in both sequences is the same.
However, there's a twist - you are allowed to multiply at most one element of by a given integer before finding this lowest -gcd equivalent sequence. You are allowed to not multiply by at all and keep the same sequence. Additionally, it is guaranteed that . You aim to minimize the resulting sequence lexicographically among all possible choices of preprocessing (or choosing not to) of .
Write a program that solves this problem.
输入格式
The first line of the input contains one integer , the number of test cases. Each test case consists of three positive integers , , and , followed by positive integers .
输出格式
For each test case, output integers representing the lexicographically lowest -gcd equivalent sequence to after performing the allowed preprocessing.
样例
样例输入 1
2
3 2 1
2 6 4
4 2 3
7 3 6 9
样例输出 1
2 4 6
3 6 9 21
数据范围与提示
Explanation
Two test cases. For the first one, no preprocessing is required. The -gcd property is satisfied since the greatest common divisor of all pairs remains 2. For the second one, preprocessing by multiplying the first element by results in the lexicographically lowest sequence .
Constraints
(over all test cases)
, is either or prime
Subtasks
Subtask
Points
Required subtasks
Other constraints
for
The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.
