给定一个长度为 $$$2n$$$ 的数组 $$$a$$$,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数,正好两次。
您还得到一个整数 $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$)。
您需要找到两个数组 $$$l$$$ 和 $$$r$$$,每个数组的长度为 $$$\mathbf{2k}$$$,这样:
- $$$l$$$ 是 $$$[a_1, a_2, \ldots a_n]$$$ 的子集$$$^\dagger$$$
- $$$r$$$ 是 $$$[a_{n+1}, a_{n+2}, \ldots a_{2n}]$$$ 的子集
- $$$l$$$ 元素的按位异或等于 $$$r$$$ 元素的按位异或;换句话说, $$$l_1 \oplus l_2 \oplus \ldots \oplus l_{2k} = r_1 \oplus r_2 \oplus \ldots \oplus r_{2k}$$$
可以证明至少一对$$$l$$$和$$$r$$$总是存在。如果有多个解,则可以输出其中任意一个。
$$$^\dagger$$$ 序列 $$$x$$$ 是序列 $$$y$$$ 的子集,如果 $$$x$$$ 可以通过删除 $$$y$$$ 的几个(可能没有或全部)元素并以任意顺序重新排列元素来获得。例如,$$$[3,1,2,1]$$$、$$$[1, 2, 3]$$$、$$$[1, 1]$$$ 和 $$$[3, 2]$$$ 是 $$$[1, 1, 2, 3]$$$ 的子集,但 $$$[4]$$$ 和 $$$[2, 2]$$$ 不是 $$$[1, 1, 2, 3]$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5 \cdot 10^4$$$, $$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$)。
第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \le a_i \le n$$$)。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在 $$$a$$$ 中恰好出现两次。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^4$$$。
输出
对于每个测试用例,输出两行。
在输出的第一行,输出 $$$2k$$$ 整数 $$$l_1, l_2, \ldots, l_{2k}$$$。
在输出的第二行,输出 $$$2k$$$ 整数 $$$r_1, r_2, \ldots r_{2k}$$$。
如果有多个解,则可以输出其中任意一个。
示例
输入 #1
4 2 1 1 2 2 1 6 1 6 4 2 1 2 3 1 6 3 5 5 4 4 1 1 2 3 4 1 2 3 4 6 2 5 1 3 3 5 1 2 6 4 6 4 2
输出 #1
2 1 2 1 6 4 1 3 1 2 1 2 5 1 3 3 6 4 2 4
注意
在第一个测试用例中,我们选择 $$$l=[2,1]$$$ 和 $$$r=[2,1]$$$。 $$$[2, 1]$$$ 是 $$$[a_1, a_2]$$$ 的子集,$$$[2, 1]$$$ 是 $$$[a_3, a_4]$$$ 的子集,并且 $$$2 \oplus 1 = 2 \oplus 1 = 3$$$。
在第二个测试用例中,$$$6 \oplus 4 = 1 \oplus 3 = 2$$$。