31793번 - 공 굴리기

문제

트리 $T$는 깊이가 $N,ドル 정점이 2ドル^{N}-1$개이고 루트의 번호가 1ドル$인 포화 이진트리이다. 트리의 $i(1 \leq i \leq 2^{N - 1} - 1)$번 정점의 왼쪽 자식은 2ドルi$번 정점이고 오른쪽 자식은 2ドルi + 1$번 정점이다. 대학원에 다니는 산지니는 $T$에 공을 굴려 정점마다 공을 한 개씩 배치하려고 한다. 처음에 $T$는 비어있으며 공은 1ドル$번 정점에서 굴리기 시작한다. 산지니는 아래 규칙에 따라 공을 굴린다.

1. 공이 위치한 현재 정점의 두 자식 정점이 존재하며 둘 중 하나라도 비어있다면 다음과 같은 규칙에 따라 자식 정점으로 공을 굴려 이동시킨다.
   • 만약 두 자식 정점 중 하나만 비어있는 경우 두 자식 정점 중 비어있는 정점으로 이동시킨다.
   • 만약 두 자식 정점이 모두 비어있는 경우 두 자식 정점을 루트로 하는 두 서브트리 중 공이 더 적은 쪽으로 굴려 이동시킨다. 만약 두 서브트리의 공의 개수가 동일한 경우 현재 정점의 번호가 홀수이면 오른쪽 자식 정점으로 이동시키고 짝수이면 왼쪽 자식 정점으로 이동시킨다.
2. 현재 정점에서 공을 더 이상 굴릴 수 없다면 현재 공을 굴리는 것을 멈춘다.
3. 1ドル$번 공부터 2ドル^{N}-1$번 공까지 순서대로 트리의 모든 정점에 공이 찰 때까지 공을 굴린다.

산지니는 시간이 없어 공을 직접 굴리지 않고 2ドル^{N}-1$개의 공 중 $Q$개의 공이 도착하는 정점의 번호만 구하려고 한다. $Q$개의 공의 번호가 주어질 때, 각 공이 도착하는 정점의 번호를 구해보자!

입력

첫 번째 줄에 트리의 깊이를 나타내는 정수 $N$이 주어진다. $(1 \leq N \leq 60)$

두 번째 줄에 산지니가 번호를 구해야 하는 공의 개수를 나타내는 정수 $Q$가 주어진다. $(1 \leq Q \leq \min(2^{N} - 1, 10^5))$

세 번째 줄부터 $Q + 2$번째 줄까지 한 줄에 하나씩 공의 번호를 나타내는 정수 $K$가 주어진다. $(1 \leq K \leq 2^{N} - 1)$

출력

공의 번호가 주어질 때마다 공이 멈추는 정점의 번호를 한 줄에 하나씩 출력한다.

제한

노트

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고하세요.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.