Задача Stamps2019. Нещодавно на уроці математики Ярослав і Мирослава вивчили, що арифметичною прогресією називають послідовність чисел, у якій різниця між кожними двома сусідніми членами однакова. А невдовзі після того діти дізналися, що на честь ювілею математичного товариства столиці було випущено дві серії марок. Кожна серія складається з 𝑛 марок різної номінальної вартості, і ці 𝑛 номіналів утворюють арифметичну прогресію. Для своєї колекції марок Ярослав придбав одну з цих серій, а Мирослава — іншу. Однак, роздивляючись придбання одне одного, діти ненароком перемішали всі марки.
Знаючи номінали марок — 2𝑛 попарно різних чисел, — допоможіть дітям розділити марки на дві серії. Відомо, що це можна зробити рівно в один спосіб.
Технічні умови. Програма Stamps2019 читає з пристрою стандартного введення натуральне число 𝑛 — кількість марок у серії, 3 ⩽ 𝑛 ⩽ 100 000. У другому рядку через пропуски 2𝑛 різних натуральних чисел, менших за 109, — перемішані номінали марок. Програма виводить на пристрій стандартного виведення в порядку зростання всі номінали марок Ярославової серії, а в другий рядок — усі номінали марок Мирославиної серії (так само в порядку зростання). Діти пам’ятають, що найдешевша марка Ярослава має менший номінал, ніж найдешевша марка Мирослави.
Приклад
| Введення | Виведення |
| 4 7 9 23 3 16 15 11 2 |
2 9 16 23 3 7 11 15 |
Коментар до прикладу
Виведені у вихідний файл послідовності утворюють шукані серії марок, адже є арифметичними прогресіями: 9 − 2 = 16 − 9 = 23 − 16 та 7 − 3 = 11 − 7 = 15 − 11. Серії виведено в правильному порядку, бо 2 < 3.