406427: GYM102399 K Черепашка

K. Черепашкаограничение по времени на тест5 секундограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

У мальчика Коли есть черепашка и поле $$$2 \times n$$$. Строки поля пронумерованы от $$$1$$$ до $$$2$$$ сверху вниз, а столбцы от $$$1$$$ до $$$n$$$ слева направо.

Предположим, что в каждой клетке есть съедобный лист салата, энергетическая ценность которого в клетке поля в строке $$$i$$$ и столбце $$$j$$$ составляет $$$a_{i,j}$$$. Черепашка изначально находится в верхней левой клетке и хочет попасть в правую нижнюю. Черепашка умеет двигаться только вниз и вправо, а среди всех возможных путей она выберет тот, который максимизирует суммарную энергетическую ценность листьев салата, через которые она проходит (если таких путей несколько, она выберет произвольный из них).

Коля беспокоится, что если черепашка съест слишком много салата, то это может быть опасно для её здоровья. Поэтому он хочет переставить листья салата в таблице таким образом, чтобы минимизировать суммарную энергетическую ценность салата, который съест черепашка. Обратите внимание, что минимизировать количество перестановок листьев салата не требуется, то есть Коля просто соберёт все листья со всех клеток и разложит их заново, так чтобы в каждой клетке оказался ровно один лист.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 25$$$) — длину поля.

Вторая строка содержит $$$n$$$ целых чисел $$$a_{1, i}$$$ ($$$0 \le a_{1, i} \le 50\,000$$$), описывающих энергетическую ценность листьев салата в первой строке поля.

Третья строка содержит $$$n$$$ целых чисел $$$a_{2, i}$$$ ($$$0 \le a_{2, i} \le 50\,000$$$), описывающих энергетическую ценность листьев салата во второй строке поля.

Выходные данные

Выведите две строки по $$$n$$$ чисел в каждой — расстановку листьев салата после переупорядочивания Коли.

Если существует несколько оптимальных переупорядочиваний — выведите любое из них.

ПримерыВходные данные

2
1 4
2 3

Выходные данные

1 3 
4 2 

Входные данные

3
0 0 0
0 0 0

Выходные данные

0 0 0 
0 0 0 

Входные данные

3
1 0 1
0 0 0

Выходные данные

0 0 1
0 1 0

Примечание

В первом примере черепашка после перестановки сможет съесть салат суммарной энергетической ценности $$$1+4+2 = 7$$$.

Во втором примере черепашка съест салат суммарной энергетической ценности $$$0$$$.

В третьем примере черепашка сможет съесть салат суммарной энергетической ценности $$$1$$$.