Problem Description

Alice and Bob really enjoy playing mahjong. After becoming familiar with the rules, they became interested in “Four Concealed Triplets, Single Wait”. In this game, both Alice and Bob have already completed Four Concealed Triplets, are in tenpai, and are preparing for a “Four Concealed Triplets, Single Wait”, so we simplify the situation as follows:

• A mahjong tile can be represented by a positive integer in the range $[1, k]$. Tiles with the same number are identical, and tiles with different numbers are different.
• Alice and Bob each have $1$ tile in hand. They take turns drawing tiles; the player who draws takes the top tile of the deck. Alice goes first. After drawing, the player will have $2$ tiles in hand and must choose one tile to discard. The discarded tile is visible to both players.
• If, when drawing, the two tiles in hand are the same, or if the opponent’s currently discarded tile is the same as the tile in your hand, then that player “wins” (pinyin: he pai) and the game ends immediately.

If all tiles are drawn and no player “wins”, it is judged as an “exhaustive draw”, and the two players are considered tied.

Now Alice and Bob are extremely smart, and they already know all the tiles on the top of the deck, as well as the opponent’s hand tile. They both want to “win”; if they cannot “win” themselves, they will try their best to prevent the opponent from “winning”.

You are given an array $a$ of $n$ mahjong tiles, indexed as $1 \dots n$. There are $m$ queries. Each query gives $x, y, l, r$, meaning: if Alice’s current hand tile is $x$, Bob’s current hand tile is $y$, and all tiles $a$ with indices in $[l, r]$ are taken in order as the game deck, where tile $a_l$ is on the top of the deck, and Alice and Bob play the game as required, then what will be the final result.

The queries are independent of each other. In particular, it is guaranteed that $l$ is odd.

Input Format

Read data from standard input.

The first line contains three positive integers $n, m, k$.

The next line contains $n$ positive integers, representing $a_1, a_2 \dots a_n$ in order.

The next $m$ lines each contain four positive integers $x, y, l, r$, representing one query.

Output Format

Write to standard output.

For each query, output one character on its own line: if Alice wins, output A; if Bob wins, output B; if it is a draw, output 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

Hint

[Sample 1 Explanation]

In the $1$st query, the deck from top to bottom is $3, 4$, Alice’s hand tile is $1$, and Bob’s hand tile is $2$. It is not hard to see that this situation will lead to an “exhaustive draw”.

In the $2$nd query, the deck from top to bottom is $1, 3, 1, 5, 4, 3$, Alice’s hand tile is $5$, and Bob’s hand tile is $5$. At this time, Bob only needs to keep this $5$ all the time, and he can “win” when he draws the next $5$; and Alice cannot discard $5$, because once she discards it, Bob will “win” immediately.

In the $3$rd query, the deck from top to bottom is $1, 2, 3, 4, 1$, Alice’s hand tile is $3$, and Bob’s hand tile is $4$. In the first round, Alice draws a $1$ and discards this $1$. In the first round, Bob draws a $2$; no matter whether he discards this $2$ or not, Alice can “win” on her next turn.

[Sample 3]

See $\verb!mahjong/mahjong3.in!$ and $\verb!mahjong/mahjong3.ans!$ in the attachments.

[Sample 4]

See $\verb!mahjong/mahjong4.in!$ and $\verb!mahjong/mahjong4.ans!$ in the attachments.

[Constraints]

• Special Property A: For every query, $l = 1$ is guaranteed.
• Special Property B: For every query, $r = n$ is guaranteed.
• Special Property C: For every query, $x = y$ is guaranteed.

For $100\%$ of the data, it is guaranteed that $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$, and it is guaranteed that $l$ is odd.

Translated by ChatGPT 5