공 굴리기

트리 $T$는 깊이가 $N$이고 정점이 $2^{N}-1$개인 포화 이진트리이며, 루트의 번호는 $1$이다. $i$ ($1 \leq i \leq 2^{N - 1} - 1$)번 정점의 왼쪽 자식은 $2i$번 정점이고, 오른쪽 자식은 $2i + 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()을 사용해야 합니다.