乌龟

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

Kolya 有一只乌龟和一块 $2\times n$ 的田地。行从上到下编号为 $1,2$，列从左到右编号为 $1$ 到 $n$。每个格子里都有一片生菜叶，第 $i$ 行第 $j$ 列叶子的能量为 $a_{i,j}$。

乌龟从左上角出发，要到达右下角。它每一步只能向右或向下移动，并会在所有合法路径中选择能量总和最大的一条。

Kolya 担心乌龟吃得太多，因此希望重新排列全部 $2n$ 片生菜叶，使乌龟最终选择的路径能量尽可能小。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_{1,1},a_{1,2},\ldots,a_{1,n}$。

第三行包含 $n$ 个整数 $a_{2,1},a_{2,2},\ldots,a_{2,n}$。

输出格式

输出两行，每行 $n$ 个整数，表示全部生菜叶的一种最优重新排列。

输出必须恰好使用输入中的全部 $2n$ 个数，并保留其重数。如果最优方案不唯一，输出任意一种即可。

样例输入 1

2
1 4
2 3

样例输出 1

1 3
4 2

样例输入 2

3
0 0 0
0 0 0

样例输出 2

0 0 0
0 0 0

样例输入 3

3
1 0 1
0 0 0

样例输出 3

0 0 1
0 1 0

样例解释

在样例 1 中，重新排列后最强路径的能量为 $1+4+2=7$。样例 2 的答案为 $0$，样例 3 的答案为 $1$。

数据范围

$2\le n\le25$，$0\le a_{i,j}\le50000$。