Перед Новым годом правительство некоторой страны решило послать подарки в каждый населенный пункт своей страны и с этой целю решило отправить в путь поезд. Для каждого из 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, . . . Если решений несколько, то выдайте любое из них.