两位队长通过从编号为 $1$ 到 $N$ 的一组球员中挑选队员来组建各自的队伍。队长们轮流进行挑选，每人根据自己对剩余球员中哪一位最适合加入其队伍的判断，挑选剩余球员中的第 $k$ 位。

给定两位队长的选择（第一位队长先开始），请计算出每支队伍的球员名单。

输入格式

输入包含三行。第一行包含一个整数 $N$。第二行包含 $N/2$ 个空格分隔的整数 $a_1, a_2, \dots, a_{N/2}$，表示第一位队长的选择：在第 $(2k - 1)$ 次轮次中，第一位队长选择了剩余球员中的第 $a_k$ 位。第三行包含 $N/2$ 个空格分隔的整数 $b_1, b_2, \dots, b_{N/2}$，表示第二位队长的选择：在第 $2k$ 次轮次中，第二位队长选择了剩余球员中的第 $b_k$ 位。

输出格式

输出应包含两行，每行包含 $N/2$ 个空格分隔的整数。第一行应包含第一支队伍所选球员的名单 $x_1, x_2, \dots, x_{N/2}$，按挑选顺序排列：球员 $x_k$ 是在第 $(2k - 1)$ 次轮次中被选中的。第二行应包含第二支队伍所选球员的名单 $y_1, y_2, \dots, y_{N/2}$，按挑选顺序排列：球员 $y_k$ 是在第 $2k$ 次轮次中被选中的。

数据范围

• $2 \leqslant N \leqslant 4\,000\,000$；
• $N$ 是 $2$ 的倍数；
• 队长的选择是有效的：在每一步中，选择的数字都在 $1$ 到当前剩余球员数量之间（含边界）。

样例

样例输入 1

4
1 1
2 1

样例输出 1

1 2
3 4