사다리타기 (Ghost Leg)

Ghost Leg는 순열을 나타내는 방법이다.

Ghost Leg는 세로선 여러 개로 그린다. 세로선 하나가 섞이는 원소 하나에 대응한다. 가로선은 인접한 두 세로선을 잇고, 어떤 두 가로선도 끝점을 공유하지 않는다. 오른쪽 그림에 예시가 나와 있다.

원소의 최종 위치를 구하려면 그 원소의 세로선 맨 위에서 출발한다. 아래로 내려가다가 이 선에 처음 닿는 가로선을 만나면, 그 가로선을 따라 인접한 세로선으로 옮겨 간다. 가로선이 왼쪽으로 이어지든 오른쪽으로 이어지든 상관없이 따라간다. 이렇게 아래로 내려가며 가로선을 계속 따라가 맨 아래에 닿으면, 그 위치가 원소의 최종 위치이다.

예시에서 원소 2는 세 번째에 놓인다. 붉은 점선이 이동 경로이다. 같은 방식으로 원소 1은 네 번째, 원소 3은 첫 번째, 원소 4는 두 번째에 놓인다.

Ghost Leg가 주어졌을 때 결과 순열을 구하시오. 순열을 적용하여 원소를 바뀐 순서대로 출력하시오.

첫 줄에 양의 정수 $n$ ($1 \le n \le 100$)과 $m$ ($0 \le m \le 1{,}000$)이 주어진다. $n$은 순열을 이루는 원소의 개수이고, $m$은 가로선의 개수이다. 세로선은 왼쪽에서 오른쪽으로 1부터 $n$까지 번호가 매겨진다.

다음 $m$개의 줄에는 정수 $a$ ($1 \le a < n$)가 하나씩 주어진다. 이는 세로선 $a$와 $a+1$ 사이에 가로선이 있다는 뜻이다. 가로선은 위에서 아래 순서로 나열된다. 같은 높이에 가로선 두 개가 있는 경우는 없다.

$n$개의 줄에 정수를 한 개씩 출력한다. 첫 번째 줄에는 순열에서 첫 번째에 오는 원소를, 두 번째 줄에는 두 번째에 오는 원소를 출력하는 식으로 $n$번째 줄까지 출력한다.