Задача №114636. Черепашка
У мальчика Коли есть черепашка и поле \(2 \times n\). Строки поля пронумерованы от \(1\) до \(2\) сверху вниз, а столбцы от \(1\) до \(n\) слева направо.
Предположим, что в каждой клетке есть съедобный лист салата, энергетическая ценность которого в клетке поля в строке \(i\) и столбце \(j\) составляет \(a_{i,j}\) (\(a_{i,j}\) равно нулю или единице). Черепашка изначально находится в верхней левой клетке и хочет попасть в правую нижнюю. Черепашка умеет двигаться только вниз и вправо, а среди всех возможных путей она всегда выберет тот, который максимизирует суммарную энергетическую ценность листьев салата, через которые она проходит (если таких путей несколько, она выберет произвольный из них).
Коля беспокоится, что если черепашка съест слишком много салата, то это может быть опасно для её здоровья. Поэтому он хочет переставить листья салата таким образом, чтобы минимизировать суммарную энергетическую ценность салата, которую съест черепашка. Обратите внимание, что минимизировать количество перестановок листьев салата не требуется, то есть Коля просто соберёт все листья со всех клеток и разложит их заново, так чтобы в каждой клетке оказался ровно один лист.
Первая строка содержит одно целое число \(n\) (\(2 \le n \le 100\,000\)) — длину поля.
Вторая строка содержит \(n\) целых чисел \(a_{1, i}\) (\(0 \le a_{1, i} \le 1\)), описывающих энергетическая ценность листов салата в первой строке поля.
Третья строка содержит \(n\) целых чисел \(a_{2, i}\) (\(0 \le a_{2, i} \le 1\)), описывающих энергетическую ценность листьев салата во второй строке поля.
Выведите две строки по \(n\) чисел в каждой — расстановку листьев салата после переупорядочивания Коли.
Если существует несколько оптимальных переупорядочиваний — выведите любое из них.
В первом примере черепашка съест салат суммарной энергетической ценности \(0\).
Во втором примере черепашка сможет съесть салат суммарной энергетической ценности \(1\).
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