숲 속의 과학자

숲 속 마을에 흰곰, 흑곰, 토끼가 살고 있다. 흰곰은 흑곰에게 연어를 주고 $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=\\{x\_1,x\_2,\cdots ,x\_N\\}$으로 만든 트리의 에너지는

\[E=\sum_{i=1}^{N}{\frac{x_i}{\left( N+1 \right)^{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}$을 공백으로 구분하여 출력한다.