Вам даны две перестановки \(a\) и \(b\) длины \(n\). Перестановкой называется массив из \(n\) элементов от \(1\) до \(n\), в котором все элементы различны. К примеру, массив [\(2,1,3\)] является перестановкой, а [\(0,1\)] и [\(1,3,1\)] не являются.
Вы можете сколько угодно раз выбрать два индекса \(i\) и \(j\), а затем поменять местами элементы \(a_i\) с \(a_j\) и \(b_i\) с \(b_j\) одновременно.
Вы ненавидите инверсии и поэтому хотите минимизировать суммарное число инверсий в обеих перестановках.
Инверсией в перестановке \(p\) называется пара индексов \((i, j)\), такая что \(i < j\) и \(p_i > p_j\). Например, если \(p=[3,1,4,2,5]\), то количество инверсий в этой перестановке равно \(3\) (искомые пары индексов: \((1,2)\), \((1,4)\) и \((3,4)\)).
Выходные данные
Для каждого набора входных данных выведите две перестановки \(a'\) и \(b'\) — перестановки после применения операций. Суммарное количество инверсий в \(a'\) и \(b'\) должно быть минимально возможным среди всех пар перестановок, которые возможно получить с помощью операций из условия.
Если существует несколько решений, выведите любое из них.
Примечание
В первом тесте минимальное достижимое количество инверсий равно \(10\).
Во втором наборе входных данных можно отсортировать обе перестановки одновременно. Для этого можно применить следующие операции:
- Поменять элементы на позициях \(1\) и \(3\) в обеих перестановках. После операции \(a =\) [\(2,1,3\)], \(b =\) [\(2,1,3\)].
- Поменять элементы на позициях \(1\) и \(2\). После операции \(a\) и \(b\) отсортированы.
В третьем тесте минимальное достижимое количество инверсий равно \(7\).