압정

시간 제한2초메모리 제한1024 MB

요약

N과 질의 K가 주어질 때, 구간에 꽂힌 프랙탈 핀 중 K번째 핀의 위치를 구합니다. 핀이 K개보다 적으면 NIE를 출력합니다.

난이도: 보통10점 중 6점
유형: 분할 정복, 재귀, 수학
정답자: 아직 제출이 없습니다

문제

Bajtosia는 수직선에 압정을 꽂습니다. 더 정확히 말하면, 자연수 N을 골라 자신이 좋아하는 구간 $[0, 3N]$ 에 압정을 꽂습니다. 처음 두 압정은 구간의 시작점과 끝점에 꽂힙니다. 그다음 Bajtosia는 다음 계획을 따릅니다.

먼저 시작점에서 길이의 3분의 1 떨어진 곳과 끝점에서 길이의 3분의 1 떨어진 곳에 새 압정을 꽂습니다. 이 두 점이 구간을 길이가 같은 세 부분, 즉 왼쪽, 가운데, 오른쪽 부분으로 나눕니다. 이어서 왼쪽 부분(양 끝에는 이미 압정이 있음)에 같은 과정을 반복하고, 오른쪽 부분에도 반복합니다. 가운데 부분에는 반복하지 않습니다. 두 부분 안에는 더 작은 구간이 생기며, Bajtosia는 그 안에서도 가능한 한 계속 이 계획을 반복합니다. 압정은 정수 지점에만 꽂으므로, 길이가 1인 구간은 더 나누지 않습니다.

최종적으로 만들어진 압정의 배치를 프랙탈이라고 부릅니다.

예를 들어 N = 3이면 구간에 다음과 같은 점들이 표시됩니다.

Bajtosia는 자신이 틀렸는지 확인하려고 여러 K에 대해 왼쪽에서 K번째 압정의 위치를 구해 봅니다. N과 Bajtosia의 질문들을 입력받아, 각 질문 K_i마다 K_i번째 압정이 어디에 있는지 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 자연수 N ( $1 \le N \le 36$ )이 주어집니다. 두 번째 줄에는 질문의 개수를 나타내는 자연수 Q ( $1 \le Q \le 200\,000$ )가 주어집니다. 이어지는 Q개의 줄에는 각각 하나의 질문이 주어집니다. 각 질문은 정수 K_i ( $1 \le K_i \le 10^{18}$ ) 하나로, 왼쪽에서 K_i번째 압정의 위치를 묻습니다. 압정은 1부터 시작하는 자연수 순서로 번호가 매겨집니다.

출력

정확히 Q줄을 출력합니다. i번째 줄에는 i번째 질문의 답, 즉 구간 위에서 K_i번째 압정의 위치를 출력합니다. Bajtosia가 꽂은 압정이 K_i개보다 적으면, 그 질문에는 대신 NIE를 출력합니다.

예제3

예제 1
입력
```
3
3
10
2
50
```
예상 출력
```
19
1
NIE
```
예제 2
입력
```
1
3
4
5
3
```
예상 출력
```
3
NIE
2
```
예제 3
입력
```
2
2
1
1000000000000000000
```
예상 출력
```
0
NIE
```