题目描述

Yousef 给了你一个长度为 $n$ 的正整数数组 $a$。

定义 $f(a)$ 表示 $a$ 的所有子数组中，元素乘积能被 $6$ 整除的子数组的数量。

更具体地说，对于每对下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$，考虑子数组 $a_l, a_{l+1}, \dots, a_r$。如果该子数组的元素乘积能被 $6$ 整除，则计入 $f(a)$。

例如，若 $a = [1, 6, 2]$，则乘积能被 $6$ 整除的子数组为 $[6]$、$[1, 6]$、$[6, 2]$ 以及 $[1, 6, 2]$，因此 $f(a) = 4$。

你的任务是重新排列数组 $a$ 的元素，使得 $f(a)$ 最小。如果有多种方式满足条件，你可以输出任意一种。

注意：$^\ast$ 当数组 $b$ 可以通过从数组 $a$ 的开头和末尾各删除零个或若干个元素得到时，$b$ 被称为 $a$ 的子数组。

输入格式

输入第一行为一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。

每个测试用例的第一行为一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组的长度。

接下来一行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，输出重新排列后的数组 $a$，使 $f(a)$ 最小。如果有多种答案，可以输出任意一种。

样例

5
6
12 7 9 4 18 5
4
3 6 2 8
7
1 10 15 20 3 6 9
5
11 14 21 2 5
3
6 6 6

12 18 4 7 5 9
2 8 3 6
6 10 20 1 15 3 9
21 5 11 2 14
6 6 6

样例说明

在第一个测试用例中，一种最优的排列是 $a = [12, 18, 4, 7, 5, 9]$。其中乘积能被 $6$ 整除的子数组为：

• $[12]$
• $[18]$
• $[12, 18]$
• $[18, 4]$
• $[12, 18, 4]$
• $[18, 4, 7]$
• $[12, 18, 4, 7]$
• $[18, 4, 7, 5]$
• $[4, 7, 5, 9]$
• $[12, 18, 4, 7, 5]$
• $[18, 4, 7, 5, 9]$
• $[12, 18, 4, 7, 5, 9]$

因此 $f(a) = 12$。可以证明不存在更优的排列使得 $f(a)$ 更小。

由 ChatGPT 5 翻译

来源

Codeforces 2227C，英文题名 Snowfall。