У Курони есть \(n\) дочерей. В качестве подарков им он купил \(n\) ожерелий и \(n\) браслетов:
- \(i\)-е ожерелье имеет яркость \(a_i\), где все \(a_i\) попарно различны (то есть все \(a_i\) имеют различные значения);
- \(i\)-й браслет имеет яркость \(b_i\), где все \(b_i\) попарно различны (то есть все \(b_i\) имеют различные значения).
Курони хочет дать ровно одно ожерелье и ровно один браслет каждой из своих дочерей. Чтобы все они выглядели уникально, общие яркости обоих подарков, вручаемых каждой дочери, должны быть попарно различными. Формально, если \(i\)-я дочь получает ожерелье с яркостью \(x_i\) и браслет с яркостью \(y_i\), то суммы \(x_i + y_i\) должны быть попарно различными. Помогите Курони раздать подарки.
Например, если яркости равны \(a = [1, 7, 5]\) и \(b = [6, 1, 2]\), то мы можем распределить подарки следующим образом:
- Дать третье ожерелье и первый браслет первой дочери, чтобы получить общую яркость \(a_3 + b_1 = 11\).
- Дать первое ожерелье и третий браслет второй дочери, чтобы получить общую яркость \(a_1 + b_3 = 3\).
- Дать второе ожерелье и второй браслет третьей дочери, чтобы получить общую яркость \(a_2 + b_2 = 8\).
А вот пример неправильного распределения:
- Дать первое ожерелье и первый браслет первой дочери, чтобы получить общую яркость \(a_1 + b_1 = 7\).
- Дать второе ожерелье и второй браслет второй дочери, чтобы получить общую яркость \(a_2 + b_2 = 8\).
- Дать третье ожерелье и третий браслет третьей дочери, чтобы получить общую яркость \(a_3 + b_3 = 7\).
Это распределение неправильное, так как общие яркости подарков, полученных первой и третьей дочерью равны. Не расстраивайте их так!
Выходные данные
Для каждого набора входных данных в первой строке выведите \(n\) целых чисел \(x_1, x_2, \dots, x_n\), обозначающих, что \(i\)-я дочь получит ожерелье с яркостью \(x_i\). Во второй строке выведите \(n\) целых чисел \(y_1, y_2, \dots, y_n\), обозначающих, что \(i\)-я дочь получит браслет с яркостью \(y_i\).
Суммы \(x_1 + y_1, x_2 + y_2, \dots, x_n + y_n\) должны быть попарно различными. Числа \(x_1, \dots, x_n\) должны быть равны числам \(a_1, \dots, a_n\) в каком-то порядке, а числа \(y_1, \dots, y_n\) должны быть равны числам \(b_1, \dots, b_n\) в каком-то порядке.
Можно показать, что решение всегда существует. Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных достаточно дать \(i\)-е ожерелье и \(i\)-й браслет \(i\)-й дочери. Соответствующие суммы будут равняться \(1 + 8 = 9\), \(8 + 4 = 12\), и \(5 + 5 = 10\).
Второй набор входных данных описан в условии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
1 8 5
8 4 5
3
1 7 5
6 1 2
|
1 8 5
8 4 5
5 1 7
6 2 1
|