Вам дан массив \(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]\).
Выходные данные
Для каждого набора входных данных выведите две строки.
В первой строке выведите \(2k\) чисел \(l_1, l_2, \ldots, l_{2k}\).
Во второй строке выведите \(2k\) чисел \(r_1, r_2, \ldots r_{2k}\).
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных можно выбрать \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
2 1
2 1
6 4
1 3
1 2
1 2
5 1 3 3
6 4 2 4
|