Description

Little A and Little B are two snakes. They are playing a game on a special tree.

The structure of this tree is as follows: first, there is a chain of length $n$, called the "main chain". The main chain consists of the $n$ nodes $1$ to $n$. On the main chain, adjacent numbered nodes are connected by an edge; otherwise, there is no edge.

Each node on the main chain has another chain attached to it, called a "side chain". The length (number of nodes) of the side chain attached to the $i$-th node on the main chain is $x_i$.

At the beginning, both Little A and Little B are on the main chain. Specifically, Little A's tail is at node $a$, and its head is at node $b$; Little B's head is at node $c$, and its tail is at node $d$. It satisfies $1\le a<b<c<d\le n$.

The rules of the game are:

• Little A and Little B move alternately, and Little A moves first.
• When a snake moves, it tries to move its whole body by one node in some direction, but it cannot move toward its original tail direction, i.e., the snake cannot move backward. After the move, the snake's head must not overlap with any part of the other snake.
• When a snake cannot move, the game ends and the opponent wins.

Now there are $q$ queries. Each query gives $a,b,c,d$. You need to determine, when both snakes play optimally, which snake will win.

Input Format

The first line contains two positive integers $n,q$.

The second line contains $n$ positive integers, representing $x_i$.

The next $q$ lines each contain four positive integers, representing $a,b,c,d$ for this query.

Output Format

Output a total of $q$ lines.

For each query, output A or B, indicating the snake that will eventually win.

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

Hint

This problem uses bundled testdata.

• Subtask 1 (10 points): $n,q \le500$.
• Subtask 2 (10 points): $n\le10^5$, $q\le500$.
• Subtask 3 (5 points): all $x_i$ are equal.
• Subtask 4 (10 points): in all queries, the sum of the lengths of Little A and Little B does not exceed $5\times10^7$.
• Subtask 5 (15 points): $x_i$ are randomly generated in $[1,10^9]$.
• Subtask 6 (20 points): $n\le5\times10^3$.
• Subtask 7 (30 points): no special constraints.

For $100\%$ of the testdata, $1\le n,q\le5\times10^5$, $1\le x_i\le10^9$, $1\le a<b<c<d\le n$.

The length of Little A is defined as $b-a+1$, and the length of Little B is defined as $d-c+1$.

Translated by ChatGPT 5