새해 기차

새해를 맞아 어떤 나라의 정부가 마을 N개에 선물을 보내기로 했다. 마을 하나마다 선물을 실은 화차를 한 량씩 준비했으므로 기차는 모두 N량이다. 기차는 마을에 닿을 때마다 맨 뒤 화차를 떼어 놓고 다음 마을로 떠나기 때문에, 화차는 정해진 순서대로 이어져 있어야 한다. 그런데 출발 직전에 짐을 싣던 인부가 화차 번호를 보지 않고 선물을 아무 순서로나 실었다는 사실이 드러났다. 기차 중간에서 화차를 빼낼 수는 없고, 선물을 다시 옮겨 실을 시간도 없다.

다행히 근처에 평행한 선로 M개가 놓인 차량기지가 있다. 화차는 기지 입구에 늘어선 순서대로 한 량씩 들어가며, 입구에서 M개 선로 가운데 어느 곳으로든 보낼 수 있다. 한 선로에 들어간 화차는 들어간 순서 그대로 반대편 출구로 나온다. 즉 선로 하나는 선입선출 대기열처럼 움직인다.

화차가 출구에서 1, 2, 3, ..., N번 순서로 나오도록 각 화차를 선로에 배정하라.

첫째 줄에 화차의 수 N과 선로의 수 M이 주어진다. ($1 \le N \le 800000$, $1 \le M \le 100000$, $M \le N$)

둘째 줄에 기지 입구에 늘어선 순서대로 화차 번호 N개가 주어진다. 화차 번호는 1부터 N까지의 수를 한 번씩 사용한다.

주어진 선로 M개로 항상 재배열할 수 있음이 보장된다.

첫째 줄에 입력에 주어진 순서대로 각 화차가 들어갈 선로 번호 N개를 공백 하나로 구분해 출력한다.

둘째 줄에 화차가 기지를 떠나는 순서, 즉 1번 화차부터 N번 화차까지 각 화차가 놓인 선로 번호 N개를 공백 하나로 구분해 출력한다.

선로 번호는 1 이상 M 이하이다. 조건을 만족하는 배정이 여러 가지면 첫째 줄에 적히는 수열이 사전순으로 가장 앞서는 것을 출력한다. 둘째 줄은 첫째 줄에서 결정된다.