거품은 어디에 있는가?

문제

컴퓨터가 가장 자주 하는 일 가운데 하나가 여러 값을 순서대로 늘어놓는 정렬이다. 그래서 정렬은 가장 많이 연구된 연산이기도 하다.

아주 단순한 정렬 알고리즘으로 버블 정렬이 있다. 버블 정렬은 여러 번의 턴으로 이루어진다. 한 턴에서 알고리즘은 수열을 훑으면서 인접한 두 원소의 순서가 잘못되어 있으면 그 두 원소를 교환한다. 한 턴 동안 교환이 한 번도 일어나지 않으면 알고리즘이 끝난다.

이름이 버블 정렬인 이유는 턴이 거듭되는 동안 작은 원소, 곧 "가벼운" 원소가 물속의 거품처럼 정렬된 수열에서 자기 자리인 앞쪽으로 올라가기 때문이다. 아래는 이 알고리즘을 의사 코드로 적은 것이다.

i를 1부터 N까지 반복
  j를 N - 1부터 i까지 하나씩 줄이며 반복
    만약 seq[j - 1] > seq[j] 이면
      seq[j - 1]과 seq[j]를 교환한다
    끝-만약
  끝-반복
  만약 이번 턴에 교환이 한 번도 없었으면
    알고리즘을 끝낸다
  끝-만약
끝-반복

예를 들어 수열 $[5, 4, 3, 2, 1]$ 을 위 알고리즘으로 정렬하면 네 번의 턴이 필요하다. 첫 번째 턴에서는 1과 2, 1과 3, 1과 4, 1과 5를 교환하므로 교환이 네 번 일어난다. 두 번째 턴에서는 2와 3, 2와 4, 2와 5를 교환해 세 번, 세 번째 턴에서는 3과 4, 3과 5를 교환해 두 번, 네 번째 턴에서는 4와 5를 교환해 한 번 일어난다. 다섯 번째 턴에서는 교환이 없으므로 알고리즘이 끝난다.

버블 정렬은 이해하기 쉽고 정당성을 증명하기도 쉽고 구현도 간단하지만 매우 비효율적이다. 실행 중에 일어나는 원소 비교 횟수가 평균적으로 $N^2$ 에 비례하는데, 여기서 $N$ 은 수열의 길이다. 당신이 할 일은 버블 정렬을 거꾸로 되짚는 것이다. 수열의 길이, 정렬에 필요한 턴의 수, 각 턴에서 일어난 교환 횟수가 주어질 때, 버블 정렬로 정렬하면 각 턴의 교환 횟수가 그대로 나오는 수열 하나를 찾아내야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$ 과 $M$ 이 주어진다. $N$ 은 정렬할 수열의 원소 개수이고, $M$ 은 버블 정렬로 그 수열을 정렬하는 데 필요한 턴의 수다 ( $1 \le N \le 100000$ , $0 \le M \le 100000$ ).

둘째 줄에는 $M$ 개의 정수 $X_1, X_2, \ldots, X_M$ 이 공백으로 구분되어 주어진다. $X_i$ 는 $i$ 번째 턴에서 일어난 교환의 횟수다 ( $1 \le X_i \le N - 1$ ). $M = 0$ 이면 둘째 줄은 빈 줄이다.

입력의 마지막 줄에는 $N = M = 0$ 이 주어지며, 이 줄은 테스트 케이스가 아니다. 모든 테스트 케이스에는 조건을 만족하는 수열이 적어도 하나 있다. 입력 전체에서 $N$ 의 합과 $M$ 의 합은 각각 200000을 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 $\{1, 2, \ldots, N\}$ 의 순열을 출력한다. 이 순열을 버블 정렬로 정렬하면 입력에 주어진 턴의 수와 각 턴의 교환 횟수가 그대로 나와야 한다. 인접한 두 원소 사이에는 공백을 하나 둔다.

조건을 만족하는 순열이 둘 이상이면 그중 사전순으로 가장 큰 것을 출력한다. 순열 $a_1, a_2, \ldots, a_N$ 이 순열 $b_1, b_2, \ldots, b_N$ 보다 사전순으로 크다는 것은, 어떤 $i$ ( $1 \le i \le N$ )에 대해 $a_i > b_i$ 이면서 앞부분 $a_1, a_2, \ldots, a_{i-1}$ 이 $b_1, b_2, \ldots, b_{i-1}$ 과 같다는 뜻이다.

다시 말해 첫 번째 원소가 가능한 한 큰 순열을 출력하고, 그런 순열이 여럿이면 그중 두 번째 원소가 가능한 한 큰 것을, 앞의 두 조건을 모두 만족하는 순열이 여럿이면 그중 세 번째 원소가 가능한 한 큰 것을 고르는 식으로 계속한다.