Suffix Array for Thue-Morse

A Thue-Morse string of order $k$ is a string of length $2^{k}$ in which the $i$-th symbol is A if the number of $1$-bits in the binary representation of $i - 1$ is even, and B if it is odd.

A suffix array for a string $s$ of length $n$ is a permutation $suf$ of the integers from $1$ to $n$ such that $s[suf[1]..n], s[suf[2]..n], \ldots, s[suf[n]..n]$ is the list of all non-empty suffixes of $s$ in lexicographical order.

Let $suf$ be the suffix array for the Thue-Morse string of order $k$. Compute the $q$ values $suf[p_1], suf[p_2], \ldots, suf[p_q]$.

The first line contains two integers $k$ and $q$, the order of the Thue-Morse string and the number of queries ($0 \le k \le 60$, $1 \le q \le 10^5$).

The second line contains $q$ integers $p_1, p_2, \ldots, p_q$, separated by spaces. These are the indices to query ($1 \le p_i \le 2^k$).

Print the $q$ answers separated by spaces.

The Thue-Morse string of order $3$ is ABBABAAB.