题目描述

给你一个长度为 $2*n$ 的数组 $a$ ，它由 $1$ 到 $n$ 的每个整数组成，每个整数包含 $2$ 次。同时给你一个整数 $k(1≤k≤⌊\frac{n}{2}⌋)$ 。

你需要找出两个长度分别为 $2*k$ 的数组 $l$ 和 $r$，使得：

• $l$ 是 $[a_1,a_2,…a_n]$ 的子集。
• $r$ 是 $[a_{n+1},a_{n+2},...,a_{2n}]$ 的子集。
• $l$ 元素的异或等于 $r$ 元素的异或。换句话说：$l_1⊕l_2⊕...⊕l_{2k}=r_1⊕r_2⊕...r_{2k}$ 的子集。

至少有一对 $l$ 和 $r$ 是存在的。如果有多个解，可以输出其中任意一个。

序列 $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]$ 的子集。

输入格式

第一行包含 $2$ 个整数 $n$ 和 $k$ $(2≤n≤5⋅10^4 , 1≤k≤⌊\frac{n}{2})$。

第二行包含 $2*n$ 个整数 $a_1,a_2,...,a_{2n}(1 \leq a_i \leq n)$。保证从 $1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。

输出格式

输出两行。

在第一行输出中，输出 $2*k$ 个整数 $l_1,l_2,...,l_{2k}$。

在第二行输出中，输出 $2*k$ 个整数 $r_1,r_2,...,r_{2k}$。

如果有多个解，可以输出其中任意一个。

样例

样例输入1

2 1
1 2 2 1

样例输出1

2 1
2 1

样例输入2

6 1
6 4 2 1 2 3 1 6 3 5 5 4

样例输出2

6 4
1 3

样例输入3

4 1
1 2 3 4 1 2 3 4

样例输出3

1 2
1 2

提示

样例 $1$ 中，我们选择 $l=[2,1]$ 和 $r=[2,1]$ 。 $[2,1]$ 是 $[a_1,a_2]$ 的子集， $[2,1]$ 是 $[a\_3,a\_4]$ 的子集。$2⊕1=2⊕1=3$ ，满足题意。

样例 $2$ 中，$6⊕4=1⊕3=2$ ，满足题意。