四暗刻单骑

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$ | $3$ | $3$ | A, B | | $2$ | $5$ | $5$ | $5$ | 无 | | $3\sim 5$ | $100$ | $100$ | $100$ | 无 | | $6\sim 7$ | $2000$ | $2000$ | $2000$ | 无 | | $8\sim 10$ | $5\times 10^4$ | $50$ | $5\times 10^4$ | 无 | | $11$ | $2\times 10^5$ | $2\times 10^5$ | $2$ | 无 | | $12$ | $2\times 10^5$ | $2\times 10^5$ | $80$ | 无 | | $13$ | $2\times 10^5$ | $2\times 10^5$ | $2\times 10^5$ | A, B | | $14\sim 15$ | $2\times 10^5$ | $2\times 10^5$ | $2\times 10^5$ | B | | $16$ | $2\times 10^5$ | $2\times 10^5$ | $2\times 10^5$ | C | | $17\sim 20$ | $10^5$ | $10^5$ | $10^5$ | 无 | | $21\sim 25$ | $2\times 10^5$ | $2\times 10^5$ | $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$ 是奇数**。