숲 속의 과학자

숲 속 마을에 흰곰, 흑곰, 토끼가 살고 있다. 흰곰은 흑곰에게 연어를 주고 $N$개의 정점을 구입했다. 정점에는 $1$부터 $N$까지 번호가 적혀 있다. 흑곰은 $N$개의 정점을 상자에 담아 흰곰에게 주었고, 흰곰은 상자를 들고 실험실로 돌아갔다.

흰곰은 $N$개의 정점으로 이진 탐색 트리를 만드는 실험을 했다. 이진 탐색 트리는 각 정점이 많아야 하나의 왼쪽 자식과 많아야 하나의 오른쪽 자식을 갖는 트리이다. 임의의 정점 $x$에 대해, 정점 $x$의 왼쪽 서브트리에는 $x$보다 작은 번호만 적혀 있고 오른쪽 서브트리에는 $x$보다 큰 번호만 적혀 있다.

흰곰의 연구 노트. 상자에서 $N$개의 정점을 꺼내 나열한다. 이것은 수열 $X=\{x_1,x_2,\cdots,x_N\}$으로 나타낼 수 있다. 정점 $x_1$을 루트로 정한다. 정점 $x_2,\cdots,x_M$을 순서대로 트리에 추가한다. 과정이 진행되는 동안 트리는 항상 루트가 $x_1$인 이진 탐색 트리이다. 루트를 제외한 모든 정점의 부모 정점은 한 번 결정되면 변하지 않는다.

정점 $u$와 정점 $v$를 잇는 경로에 포함된 간선의 개수를 $d(u,v)$라고 하자. 루트가 $x_1$인 트리의 높이는 $H=\max_{1\le i\le N} d(x_1,x_i)$ 이다.

수열 $X$로 만든 트리의 에너지는 $E=\sum_{i=1}^{N}\frac{x_i}{(N+1)^{i-H}}$ 이다.

흰곰은 $N!$번의 실험 끝에 에너지 $E$를 최소화하는 수열 $X$를 찾아내고, 이를 풀잎에 기록해 두었다. 흰곰이 실험을 마치고 동굴에 들어가 잠든 사이에 토끼가 풀잎의 일부를 먹어 버렸다. 잠에서 깬 흰곰은 이를 보고 슬퍼했다. 토끼는 자신이 먹어 없앤 수열의 일부를 계산해서 흰곰에게 알려주기로 했다.

$M$개의 정수 $p_1,p_2,\cdots,p_M$이 주어진다. 에너지 $E$를 최소화하는 수열 $X$에 대해 $x_{p_1},x_{p_2},\cdots,x_{p_M}$을 구하시오.

첫 번째 줄에 $N$, $M$이 공백으로 구분되어 주어진다. ($2\le N\le 10^{18}$, $1\le M\le\min(N,2\times 10^5)$)

두 번째 줄에 $p_1,p_2,\cdots,p_M$이 공백으로 구분되어 주어진다. ($1\le p_i\le N$, $p_i<p_{i+1}$)

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에 $x_{p_1},x_{p_2},\cdots,x_{p_M}$을 공백으로 구분하여 출력한다.