Thue-Morse 문자열의 접미사 배열

차수가 $k$인 Thue-Morse 문자열은 길이가 $2^{k}$인 문자열이다. 이 문자열의 $i$번째 글자는 $i - 1$의 이진 표현에 있는 1의 개수가 짝수이면 A, 홀수이면 B이다.

길이가 $n$인 문자열 $s$의 접미사 배열은 $1$부터 $n$까지의 정수로 이루어진 순열 $suf$이다. $s[suf[1]..n], s[suf[2]..n], \ldots, s[suf[n]..n]$이 $s$의 공백이 아닌 모든 접미사를 사전순으로 나열한 목록이 되도록 정한다.

차수가 $k$인 Thue-Morse 문자열의 접미사 배열을 $suf$라고 하자. $suf[p_1], suf[p_2], \ldots, suf[p_q]$의 $q$개 값을 구한다.

첫 줄에 Thue-Morse 문자열의 차수 $k$와 질의의 개수 $q$가 주어진다 ($0 \le k \le 60$, $1 \le q \le 10^5$).

둘째 줄에는 공백으로 구분된 $q$개의 정수 $p_1, p_2, \ldots, p_q$가 주어진다. 이는 구해야 할 인덱스이다 ($1 \le p_i \le 2^k$).

$q$개의 답을 공백으로 구분하여 출력한다.

차수가 $3$인 Thue-Morse 문자열은 ABBABAAB이다.