← 返回题目列表

Codeforces · 1859/A

A. 我们团结一致

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,包含整数。有两个最初为空的数组 $$$b$$$ 和 $$$c$$$。您需要将数组 $$$a$$$ 的每个元素添加到数组 $$$b$$$ 或 $$$c$$$ 之一,以满足以下条件:

- 数组 $$$b$$$ 和 $$$c$$$ 都非空。更正式地说,令 $$$l_b$$$ 为数组 $$$b$$$ 的长度,$$$l_c$$$ 为数组 $$$c$$$ 的长度。然后$$$l_b, l_c \ge 1$$$。
- 对于任意两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$),$$$c_j$$$ 不是 $$$b_i$$$ 的约数。

输出能得到的数组$$$b$$$和$$$c$$$,如果不存在则输出$$$-1$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,如果解不存在,则输出单个整数 $$$-1$$$。

否则,在第一行中,输出两个整数 $$$l_b$$$ 和 $$$l_c$$$ — 分别是数组 $$$b$$$ 和 $$$c$$$ 的长度。

在第二行中,输出 $$$l_b$$$ 整数 $$$b_1, b_2, \ldots, b_{l_b}$$$ — 数组 $$$b$$$ 的元素。

在第三行中,输出 $$$l_c$$$ 整数 $$$c_1, c_2, \ldots, c_{l_c}$$$ — 数组 $$$c$$$ 的元素。

如果有多个解,则输出其中任意一个。您可以按任意顺序输出数组的元素。

示例

输入 #1

5
3
2 2 2
5
1 2 3 4 5
3
1 3 5
7
1 7 7 2 9 1 4
5
4 8 12 12 4

输出 #1

-1
3 2
1 3 5 
2 4 
1 2
1 
3 5 
2 5
1 1 
2 4 7 7 9 
3 2
4 8 4 
12 12

注意

在第一个测试用例中,不存在解决方案。

在第二个测试用例中,我们可以得到 $$$b = [1, 3, 5]$$$ 和 $$$c = [2, 4]$$$。那么元素 $$$2$$$ 和 $$$4$$$ 不会整除元素 $$$1、3$$$ 和 $$$5$$$。

在第五个测试用例中,我们可以得到 $$$b = [4, 8, 4]$$$ 和 $$$c = [12, 12]$$$。