19500번 - Suffix Array for Thue-Morse 다국어

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

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

Let $\mathit{suf}$ be the suffix array for Thue-Morse string of order $k$. You task is to calculate $q$ values: $\mathit{suf}[p_1]$, $\mathit{suf}[p_2]$, $\ldots$, $\mathit{suf}[p_q]$.

The first line of input contains two integers $k$ and $q$: the order of 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: the required indices ($1 \le p_i \le 2^k$).

Output $q$ answers to the queries, separated by spaces.

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