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