Pushpins

Bajtosia pushes pins into a number line. More precisely, she picks a natural number N and pushes pins into her favorite segment $[0, 3N]$. The first two pins go at the start and the end of the segment. Then she follows this plan:

First, she pushes new pins at one third of the length from the start and at one third of the length from the end. These points split the segment into three parts of equal length: left, middle, and right. Next, she repeats the whole process for the left part (its start and end already have pins), and then for the right part, but not for the middle part. Smaller parts appear inside both of these parts, and she keeps repeating the plan in them for as long as possible. Since she only pushes pins at integer points, she stops splitting segments of length 1.

The final pin layout is called a fractal.

For example, if N = 3, the following points are marked on the segment:

Bajtosia wonders whether she made a mistake, so she checks the position of the K-th pin from the left for various K. Write a program that reads N and Bajtosia's queries, and for each query K_i finds where the K_i-th pin is located.

The first line contains one natural number N ($1 \le N \le 36$). The second line contains one natural number Q ($1 \le Q \le 200\,000$), the number of queries. Each of the next Q lines contains one query, a single integer K_i ($1 \le K_i \le 10^{18}$), asking for the position of the K_i-th pin from the left. Pins are numbered with consecutive natural numbers starting from 1.

Print exactly Q lines. Line i contains the answer to the i-th query: the position of the K_i-th pin on the segment. If Bajtosia has pushed fewer than K_i pins, print NIE for that query.