시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

3 8
1 2 3 4 5 6 7 8

예제 출력 1

6 7 4 1 8 5 3 2

힌트

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