← 返回题目列表

Codeforces · 2227/C

C. 降雪

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

Yousef 给了你一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。

设 $$$f(a)$$$ 表示 $$$a$$$ 的子数组 $$$^{\text{∗}}$$$ 的数量,其中 产品 可以被 $$$6$$$ 整除。

更正式地说,对于每对索引 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \le r \le n$$$,考虑子数组 $$$a_l, a_{l+1}, \dots, a_r$$$。如果该子数组的元素的乘积能被 $$$6$$$ 整除,则该子数组被计数。

例如,如果 $$$a = [1, 6, 2]$$$,则乘积可被 $$$6$$$ 整除的子数组为 $$$[6]$$$、$$$[1, 6]$$$、$$$[6, 2]$$$ 和 $$$[1, 6, 2]$$$,因此 $$$f(a) = 4$$$。

您的任务是对数组 $$$a$$$ 的元素重新排序,以使 $$$f(a)$$$ 最小化。如果有多种方法可以做到这一点,您可以输出其中任何一种。

$$$^{\text{*}}$$$数组 $$$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$$$。

输出

对于每个测试用例,以最小化 $$$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)$$$ 值。