B. Равный XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$2n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно дважды.

Вам также дано целое число $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).

Вам нужно найти два массива $$$l$$$ и $$$r$$$ длины $$$\mathbf{2k}$$$ каждый такие, что:

  • $$$l$$$ является подмножеством$$$^\dagger$$$ $$$[a_1, a_2, \ldots a_n]$$$
  • $$$r$$$ является подмножеством $$$[a_{n+1}, a_{n+2}, \ldots a_{2n}]$$$
  • побитовый XOR элементов $$$l$$$ равен побитовому XOR элементов $$$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}$$$.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
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
Выходные данные
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$$$.