CF1511G.Chips on a Board

Alice and Bob have a rectangular board consisting of $n$ rows and $m$ columns. Each row contains exactly one chip.

Alice and Bob play the following game. They choose two integers $l$ and $r$ such that $1 \le l \le r \le m$ and cut the board in such a way that only the part of it between column $l$ and column $r$ (inclusive) remains. So, all columns to the left of column $l$ and all columns to the right of column $r$ no longer belong to the board.

After cutting the board, they move chips on the remaining part of the board (the part from column $l$ to column $r$). They make alternating moves, and the player which cannot make a move loses the game. The first move is made by Alice, the second — by Bob, the third — by Alice, and so on. During their move, the player must choose one of the chips from the board and move it any positive number of cells to the left (so, if the chip was in column $i$, it can move to any column $j \lt i$, and the chips in the leftmost column cannot be chosen).

Alice and Bob have $q$ pairs of numbers $L_i$ and $R_i$. For each such pair, they want to determine who will be the winner of the game if $l = L_i$ and $r = R_i$. Note that these games should be considered independently (they don't affect the state of the board for the next games), and both Alice and Bob play optimally.

爱丽丝和鲍勃有一块由 $n$ 行 $m$ 列组成的矩形棋盘。每行恰好有一枚棋子。

爱丽丝和鲍勃进行如下游戏：他们选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le m$，并将棋盘沿列方向裁剪，仅保留第 $l$ 列到第 $r$ 列（含端点）之间的部分。因此，第 $l$ 列左侧的所有列和第 $r$ 列右侧的所有列均不再属于棋盘。

裁剪后，他们在剩余部分（即第 $l$ 列至第 $r$ 列）上移动棋子。双方轮流行动，无法行动的一方判负。先手为爱丽丝，第二步由鲍勃执行，第三步由爱丽丝执行，依此类推。在自己的回合中，玩家必须从棋盘上选择一枚棋子，并将其向左移动任意正整数个格子（即若该棋子当前位于第 $i$ 列，则可移至任意第 $j$ 列，其中 $j < i$；最左侧列中的棋子无法被选中）。

爱丽丝和鲍勃共有 $q$ 对数字 $(L_i, R_i)$。对每一对，他们希望确定：当 $l = L_i$ 且 $r = R_i$ 时，游戏的获胜者是谁。注意，这些游戏彼此独立（前一局的结果不会影响后续棋盘的状态），且爱丽丝与鲍勃均采用最优策略。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of rows and columns on the board, respectively.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le m$), where $c_i$ is the index of the column where the chip in the $i$-th row is located (so, the chip in the $i$-th row is in the $c_i$-th column).

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

Then $q$ lines follow, the $i$-th of them contains two integers $L_i$ and $R_i$ ($1 \le L_i \le R_i \le m$).

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示棋盘的行数和列数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le m$），其中 $c_i$ 表示第 $i$ 行中棋子所在的列号（即第 $i$ 行的棋子位于第 $c_i$ 列）。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。

接下来有 $q$ 行，其中第 $i$ 行包含两个整数 $L_i$ 和 $R_i$（$1 \le L_i \le R_i \le m$）。

Print a string of $q$ characters. The $i$-th character should be A if Alice wins the game with $l = L_i$ and $r = R_i$, or B if Bob wins it.

输出一个长度为 $q$ 的字符串。其中第 $i$ 个字符应为 A（若 Alice 在 $l = L_i$ 且 $r = R_i$ 时赢得游戏），或 B（若 Bob 赢得游戏）。