← 返回题目列表

Codeforces · 1511/G

G. 板上的芯片

中文机器翻译题面 查看原题

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$$$ 中的任何列,并且不能选择最左边一列中的筹码)。

Alice 和 Bob 有 $$$q$$$ 数对 $$$L_i$$$ 和 $$$R_i$$$。对于每一对这样的配对,如果 $$$l = L_i$$$ 且 $$$r = R_i$$$,他们想要确定谁将成为游戏的获胜者。请注意,这些游戏应该独立考虑(它们不会影响接下来游戏的棋盘状态),并且 Alice 和 Bob 都处于最佳状态。

输入

第一行包含两个整数 $$$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$$$ 字符的字符串。如果 Alice 以 $$$l = L_i$$$ 和 $$$r = R_i$$$ 赢得游戏,则第 $$$i$$$ 个字符应为 A;如果 Bob 获胜,则第 $$$i$$$ 个字符应为 B。

示例

输入 #1

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

输出 #1

BAAAAAB