题目描述

小 A 和小 B 是两条蛇，他们正在一棵特殊的树上做游戏。

这棵树的结构如下：首先有一条长度为 $n$ 的链，称为“主链”。主链由 $1$ 至 $n$ 这 $n$ 个节点构成。在主链上，编号相邻的点有边相连，否则则没有。

主链上的每一个点都挂着一条链，称为“副链”。主链上的第 $i$ 个点挂的副链长度（链上的点数）为 $x_i$。

小 A 和小 B 初始时都在主链上，具体而言，小 A 的蛇尾在点 $a$，蛇头在点 $b$，小 B 的蛇头在点 $c$，蛇尾在点 $d$。满足 $1\le a<b<c<d\le n$。

他们的游戏规则如下：

• 小 A 和小 B 轮流移动，小 A 先手。
• 每条蛇移动时，他会尝试整体向某一方向移动一个节点，但不能向原来蛇尾方向移动，也就是蛇不能倒退。需满足移动后蛇头不得与另外一条蛇的任意部分重合。
• 当一条蛇无法移动时，游戏结束，对手获胜。

现在有 $q$ 次询问，每次询问给定 $a,b,c,d$，请求出当两条蛇都采取最优策略时，哪一条蛇会获胜。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数，表示 $x_i$。

接下来 $q$ 行，每行四个正整数表示此次询问的 $a,b,c,d$。

输出格式

输出共 $q$ 行。

对于每组询问，输出 A 或 B，表示最终能获胜的蛇。

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

A
A
A
B
A
A
B
A
A
B

提示

本题采用捆绑测试。

• Subtask 1（10 points）：$n,q \le500$。
• Subtask 2（10 points）：$n\le10^5$，$q\le500$。
• Subtask 3（5 points）：所有 $x_i$ 都相等。
• Subtask 4（10 points）：所有询问中小 A 和小 B 的长度总和不超过 $5\times10^7$。
• Subtask 5（15 points）：$x_i$ 在 $[1,10^9]$ 内随机生成。
• Subtask 6（20 points）：$n\le5\times10^3$。
• Subtask 7（30 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n,q\le5\times10^5$，$1\le x_i\le10^9$，$1\le a<b<c<d\le n$。

小 A 的长度定义为 $b-a+1$，小 B 的长度定义为 $d-c+1$。