G. 棋盘上的芯片

时间限制：每个测试点 $5$ 秒 内存限制：$512$ 兆字节

题目描述

Alice 和 Bob 有一块由 $n$ 行和 $m$ 列构成的矩形棋盘。每一行恰好包含一枚棋子。

Alice 和 Bob 进行如下游戏。首先，他们选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le m$，并将棋盘裁剪为仅保留第 $l$ 列到第 $r$ 列（包含两端）的部分。因此，第 $l$ 列左侧的所有列以及第 $r$ 列右侧的所有列都将被移除。

裁剪完棋盘后，他们会在剩余棋盘部分（第 $l$ 列到第 $r$ 列）上移动棋子。双方轮流操作，不能移动棋子的一方输掉游戏。Alice 先手，Bob 第二手，Alice 第三手，依此类推。轮到某玩家时，该玩家必须选择棋盘上的一枚棋子，并将其向左移动任意正整数个格子（即，若棋子在 $i$ 列，则可以移动到任意 $j < i$ 列，但位于最左侧列的棋子不能被选择）。

共有 $q$ 对 $(L_i, R_i)$ 需要询问。对于每一对 $(L_i, R_i)$，如果取 $l = L_i$ 和 $r = R_i$，请判断游戏的结果。注意这些游戏是相互独立的（不会影响后续游戏的状态），且双方均采取最优策略。

输入:

第一行包含两个整数 $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$）。

输出:

输出一个长度为 $q$ 的字符串。第 $i$ 个字符应为 A，表示当 $l = L_i$ 且 $r = R_i$ 时 Alice 获胜；若 Bob 获胜，则为 B。

样例

输入：

8 10
1 3 3 7 4 2 6 9
7
2 3
1 3
1 4
1 10
5 10
8 10
9 10

输出：

BAAAAAB