New Year Train

For the new year, the government of one country decided to send gifts to N towns. One wagon of gifts was prepared for each town, so the train has N wagons. At every town the train drops the last wagon and leaves for the next one, so the wagons have to be coupled in the right order. Just before departure it turned out that the loading crew never looked at the wagon numbers and put the gifts in whatever order they liked. A wagon cannot be pulled out of the middle of the train, and there is no time to move the gifts again.

There is a depot nearby with M parallel tracks. The wagons enter the depot one at a time, in the order they stand at the entrance, and each wagon can be sent to any of the M tracks. A wagon that enters a track comes out of the far end in the same order it went in, so one track behaves like a first in, first out queue.

Assign every wagon to a track so that the wagons leave the depot in the order 1, 2, 3, ..., N.

The first line contains the number of wagons N and the number of tracks M. ($1 \le N \le 800000$, $1 \le M \le 100000$, $M \le N$)

The second line contains N wagon numbers in the order the wagons stand at the entrance of the depot. The numbers are 1 through N, each used once.

A valid assignment onto the given M tracks always exists.

On the first line print N track numbers, one for each wagon in the order given in the input, separated by single spaces.

On the second line print the track numbers in the order the wagons leave the depot, that is, the track of wagon 1, then of wagon 2, and so on up to wagon N, separated by single spaces.

Track numbers are between 1 and M. If several assignments satisfy the conditions, print the one whose first line is lexicographically smallest. The second line follows from the first.