题目描述

Alice 和 Bob 很喜欢打麻将。他们在对麻将规则熟悉后，开始对「四暗刻单骑」感兴趣。而在这局游戏中，Alice 和 Bob 都已经集齐了四暗刻，处于听牌状态并准备「四暗刻单骑」，于是我们将这样的局面简化如下：

• 一张麻将牌可以用一个范围在 $[1, k]$ 内的正整数表示，数字相同的牌相同，数字不同的牌不相同。
• Alice 和 Bob 手中各有 $1$ 张牌作为手牌。两人轮流进行摸牌，每次摸牌的玩家会得到一张牌堆顶部的牌，Alice 先进行。摸牌后会有 $2$ 张手牌，此时需要选择一张牌打出。打出的牌双方可见。
• 当摸牌时两张手牌相同时，或当前对方打出的牌和自己目前手牌相同时，该玩家「和牌」并获胜，游戏结束。

若牌摸完后无玩家「和牌」，则判为「荒牌流局」，此时判定两位玩家平局。

现在 Alice 和 Bob 都绝顶聪明，并且已经得知了牌堆顶部的所有牌，以及对方手牌。他们都希望自己可以「和牌」并获胜，若自己无法「和牌」就会尽可能阻止对方「和牌」。

你现在拿到了 $n$ 张麻将牌组成的 $a$ 数组，下标依次为 $1\dots n$。现在有 $m$ 次询问，每次会给定 $x, y, l, r$ 表示：若目前 Alice 手牌为 $x$，Bob 手牌为 $y$，且 按顺序 取出 $a$ 中下标为 $[l, r]$ 的所有牌作为游戏牌堆，其中牌 $a_l$ 位于牌堆顶部，Alice 和 Bob 按要求进行游戏，最后结局如何。

询问之间相互独立。特别地，保证 $l$ 为奇数。

输入格式

从标准输入中读入数据。

第一行三个正整数 $n, m, k$。

接下来一行 $n$ 个正整数，依次表示 $a_1, a_2 \dots a_n$。

接下来 $m$ 行，每行四个正整数 $x,y,l,r$，表示一次询问。

输出格式

输出到标准输出。

对于每次询问，输出一行一个字符：如果 Alice 获胜，输出 A；如果 Bob 获胜，输出 B；如果平局，输出 D。

12 3 5
2 3 1 2 3 4 1 3 1 5 4 3
1 2 5 6
5 5 7 12
3 4 3 7

D
B
A

7 6 3
2 3 3 3 1 3 3 
1 2 5 7
1 1 5 6
1 3 1 6
2 3 7 7
1 3 3 5
1 2 1 4

A
A
B
D
B
D

提示

【样例 1 解释】

在第 $1$ 组询问中，牌堆自顶至底依次是 $3, 4$，Alice 手牌为 $1$，Bob 手牌为 $2$。不难发现此局面会导致「荒牌流局」。

在第 $2$ 组询问中，牌堆自顶至底依次是 $1, 3, 1, 5, 4, 3$，Alice 手牌为 $5$，Bob 手牌为 $5$。此时 Bob 只需要一直保留这张 $5$，就可以在摸上下一张 $5$ 时「和牌」；而 Alice 不能打出 $5$，因为一旦打出就会导致 Bob 立刻「和牌」。

在第 $3$ 组询问中，牌堆自顶至底依次是 $1, 2, 3, 4, 1$，Alice 手牌为 $3$，Bob 手牌为 $4$。Alice 第一局摸上一张 $1$，她打出这张 $1$。Bob 第一局摸上一张 $2$，他无论是否打出这张 $2$，Alice 都可以在下回合「和牌」。

---

【样例 3】

见附件下的 $\verb!mahjong/mahjong3.in!$ 与 $\verb!mahjong/mahjong3.ans!$。

---

【样例 4】

见附件下的 $\verb!mahjong/mahjong4.in!$ 与 $\verb!mahjong/mahjong4.ans!$。

---

【数据范围】

测试点编号	$n\le$	$m\le$	$k\le$	特殊性质
$1$	$3$			A, B
$2$	$5$			无
$3\sim 5$	$100$
$6\sim 7$	$2000$
$8\sim 10$	$5\times 10^4$	$50$	$5\times 10^4$
$11$	$2\times 10^5$		$2$
$12$			$80$
$13$			$2\times 10^5$	A, B
$14\sim 15$				B
$16$				C
$17\sim 20$	$10^5$			无
$21\sim 25$	$2\times 10^5$

• 特殊性质 A：保证每次询问 $l = 1$。
• 特殊性质 B：保证每次询问 $r = n$。
• 特殊性质 C：保证每次询问 $x = y$。

对于 $100\%$ 的数据，保证 $3 \leq n \leq 2\times 10^5$，$1 \leq m \leq 2\times 10^5$，$1 \leq a_i, x, y \leq k \leq n$，$1 \leq l \leq r \leq n$，保证 $l$ 是奇数。