Новорічний поїзд#7483
Перед Новим роком уряд певної країни вирішив надіслати подарунки в кожний населений пункт, відправивши поїзд. Для кожного з міст і сіл виділено рівно вагон з подарунками. Маршрут побудовано так, що в першому населеному пункті, куди прибуде поїзд, буде відчеплений останній вагон, потім передостанній і так далі. Перед відправкою з'ясувалося, що вантажники не звернули уваги на нумерацію і наповнили вагони подарунками у випадковому порядку. Зняти вагон з середини складу неможливо, а часу на перерозподіл подарунків немає. Тому поїзд вирішили відправити в депо, що складається з паралельних шляхів. При вході в депо кожен вагон направляється на один з цих шляхів, а з депо вагони виводяться вже з іншого боку у правильній послідовності: 1, 2, 3, 4 і так далі.
Наприклад, якщо при вході в депо з трьома паралельними шляхами вагонів стояли в порядку 2, 5, 1, 4, 6, 3, то на перший шлях депо можна помістити вагони , на другий шлях вагони , а вагон - на третій шлях. У цьому випадку вагони можна вивести з депо в потрібному порядку.
На щастя, з'ясувалося, що наявних шляхів у депо достатньо, щоб переформувати склад потрібним чином.
У першому рядку знаходяться два цілі числа і - кількість вагонів у поїзді та кількість шляхів у депо відповідно (1 \leq n \leq 800\,000, 1 \leq m \leq 100\,000, m \leq n). У другому рядку знаходяться чисел - послідовність вагонів перед входом у депо. Гарантується, що вхідні дані такі, що задача має розв'язок.
У першому рядку запишіть чисел - для кожного вагона з початкового складу номер шляху в депо, на який треба відправити цей вагон. У другому рядку також запишіть чисел - номери шляхів у депо в тій послідовності, в якій слід з депо вагони виводити, щоб отримати порядок 1, 2, 3, \ldots Якщо розв'язків декілька, то видайте будь-який з них.
Приклад 1