Рассмотрим таблицу размера \(2 \times n\), где \(n\) является чётным числом. Вы можете разместить числа \(1, 2, \ldots, 2n\) в таблице, используя каждое число ровно один раз.
Путём называется последовательность клеток, полученная последовательным переходом из клетки \((1, 1)\) вправо или вниз, пока клетка \((2, n)\) не будет достигнута. При этом путь не должен выходить за пределы таблицы.
Стоимостью пути называется знакопеременная сумма чисел, написанных в клетках пути. Иными словами, пусть числами, написанными в клетках, являются \(a_1, a_2, \ldots, a_k\) (в порядке посещения), тогда стоимостью является \(a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}\).
Разместите числа \(1, 2, \ldots, 2n\) в таблице так, чтобы минимальная стоимость по всем путям от \((1, 1)\) до \((2, n)\) была максимальна. Если существует несколько таких таблиц с максимальным значением, выведите любую из них.
Выходные данные
Для каждого набора входных данных выведите \(2\) строки, каждая из которых содержит \(n\) целых чисел — искомую таблицу. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входные данных есть только два пути из клетки \((1, 1)\) в клетку \((2, 2)\). Их стоимости равны \(3-1+4=6\) и \(3-2+4=5\). Тогда минимальная стоимость равна \(5\), что является максимально возможным значением.
Во втором наборе входных данных есть четыре пути из клетки \((1, 1)\) в клетку \((2, 4)\). Их стоимости равны \(8-1+5-3+7=16\), \(8-2+5-3+7=15\), \(8-2+6-3+7=16\) и \(8-2+6-4+7=15\). Тогда минимальная стоимость равна \(15\), что является максимально возможным значением.