Snake Game on a Special Tree

Two snakes, A and B, are playing a game on a special tree. The tree is formed by a main chain and several branch chains. The main chain is a simple path consisting of n nodes numbered from 1 to n with an edge between every two consecutive nodes. Hanging from each node i of the main chain is a branch chain of length x_i (i.e. the branch has x_i nodes arranged as a simple chain attached to node i).

Initially both snakes lie on the main chain. Snake A’s tail is at node a and its head is at node b, and snake B’s head is at node c and its tail is at node d, with 1 ≤ a < b < c < d ≤ n. Note that snake A is oriented from node a to node b (so it naturally moves to the right) while snake B is oriented from node d to node c (so it naturally moves to the left).

The game rules are as follows:

• Snakes move alternately, with snake A moving first.
• When a snake moves, it shifts its entire body one node in one chosen direction. However, a snake cannot move toward its tail (i.e. it cannot reverse).
• The new head position must not collide with any part of the other snake.
• The game ends when the current snake cannot make any valid move; the other player is then declared the winner.

On the main chain the snakes compete for a limited number of moves. Define:

• Main chain gap M = c − b − 1. This is the number of free nodes on the main chain between the head of snake A and the head of snake B.
• At node b (snake A’s head) there is an available branch with x_b nodes; similarly, at node c (snake B’s head) there is a branch of length x_c.

The movement options for each snake are:

1. Main chain move: move the head one node along the main chain in the natural direction (i.e. rightwards for snake A and leftwards for snake B). Such moves will reduce the available main chain gap M by 1.
2. Branch move (switch): move from the main chain into the branch attached at the head. After a snake switches to its branch moves, it is isolated from the opponent. However, switching costs one branch move from the available branch moves and ends the possibility of further main chain moves.

When both snakes remain on the main chain the outcome is decided solely by the parity of M: if M is odd then snake A (the first mover) wins, and if M is even then snake B wins. However, if M is 0 then the only moves come from branch moves – in that case, snake A wins if x_b > x_c and snake B wins otherwise.

In general, when M > 0 a snake may choose to switch to its branch if doing so (given its branch length advantage) would turn a losing position on the main chain into a winning overall strategy. In our problem the optimal play can be decided by the following rule (which can be proved via game‐theoretic analysis):

• If M = 0 then the winner is A if x_b > x_c, otherwise B wins.
• If M > 0 then:
  • If M is odd, snake A wins.
  • If M is even, snake A wins if x_b > x_c, otherwise snake B wins.

Your task is to answer q queries. In each query you are given four integers a, b, c, d (satisfying 1 ≤ a < b < c < d ≤ n) which denote the current positions of the snakes on the main chain. Assuming both snakes play optimally, determine which snake will win the game.

inputFormat

The first line contains two integers n and q — the number of nodes in the main chain and the number of queries.

The second line contains n integers x1, x2, ..., xn, where xi is the length of the branch hanging from the i-th node of the main chain.

Each of the next q lines contains four integers a, b, c, d (with 1 ≤ a < b < c < d ≤ n) indicating a query.

outputFormat

For each query, output a single line containing either A if snake A wins or B if snake B wins, assuming both play optimally.

sample

6 3
0 100 5 0 0 0
1 2 4 5
1 2 5 6
1 2 3 4

A
A
B

</p>