棋盘上的棋子

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有一个 $n$ 行 $m$ 列的棋盘，每行恰有一个棋子，第 $i$ 行棋子位于第 $c_i$ 列。

每次询问给定 $L,R$，只保留第 $L$ 到第 $R$ 列及其中的棋子。两名玩家轮流把任意棋子向左移动至少一格，不能移动者输。Alice 先手，双方最优，判断胜者。

输入格式

第一行两个整数 $n,m$（$1\le n,m\le2\times10^5$）。第二行 $n$ 个整数 $c_i$（$1\le c_i\le m$）。第三行一个整数 $q$（$1\le q\le2\times10^5$），随后 $q$ 行每行两个整数 $L_i,R_i$（$1\le L_i\le R_i\le m$）。

输出格式

输出长度为 $q$ 的字符串。第 $i$ 位为 A 表示 Alice 获胜，否则为 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

数据范围

$1\le n,m,q\le2\times10^5$，$1\le c_i\le m$，$1\le L_i\le R_i\le m$。