← 返回题目列表

Codeforces · 1407/B

B. 大沃瓦

中文机器翻译题面 查看原题

Alexander是一位著名的程序员。今天,他终于决定出去踢足球,但第一击就在富商大沃瓦的新劳斯莱斯上留下了凹痕。弗拉基米尔最近在流行的在线市场“Zmey-Gorynych”上开设了一家商店,并为亚历克斯提供了一份工作:如果他通过解决任务来展示他的编程技能,他将担任网络安全专家。否则,他将在未来两年内交付一些可疑的产品。

给你 $$$n$$$ 正整数 $$$a_1, a_2, \dots, a_n$$$。一次完全使用它们中的每一个,您将创建这样的序列 $$$b_1, b_2, \dots, b_n$$$ 序列 $$$c_1, c_2, \dots, c_n$$$ 按字典顺序最大,其中 $$$c_i=GCD(b_1,\dots,b_i)$$$ - 的前 $$$i$$$ 元素的最大公约数$$$b$$$。

亚历山大确实害怕这个简单任务的条件,所以他要求你解决它。

当且仅当满足以下条件之一时,序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^3$$$) — 序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^3$$$) — 序列 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$。

输出

对于每个测试用例,在一行中输出答案 - 所需的序列 $$$b$$$。如果有多个答案,请打印其中一个。

示例

输入 #1

7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17

输出 #1

5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16

注意

在示例的第一个测试用例中,只有两种可能的排列 $$$b$$$  — $$$[2, 5]$$$ 和 $$$[5, 2]$$$:第一个 $$$c=[2, 1]$$$,第二个 $$$c=[5, 1]$$$。

在示例的第三个测试用例中,数字$$$9$$$应该是$$$b$$$中的第一个,并且$$$GCD(9, 3)=3$$$,$$$GCD(9, 8)=1$$$,因此$$$b$$$的第二个数字应该是$$$3$$$。

在示例的第七个测试用例中,前四个数字成对具有公约数(2 的幂),但它们都不能成为最佳排列 $$$b$$$ 中的第一个。