L. Games
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Agustín and Brian play many games every weekend of the following game:

Given a list of $$$m$$$ positive integers $$$x_1, x_2, \dots, x_m$$$, each player starts with $$$0$$$ points, and alternately starting with Agustín, each player on their turn performs one of these two actions:

  1. Choose one of the elements from the list that has not been chosen previously, and add the chosen number from the list to their score.
  2. Pass the turn.

If both players pass in two consecutive turns, the game ends. Note that the fact that a player has no numbers available to choose on their turn does not necessarily imply that the game ends on that turn.

When the game ends, if one player has a higher score than the other, that player wins the game, and if both players have the same score, then the result of the game is a tie.

They are tired of always playing games of the same type, so in the last few weekends, they started to consider variants. In particular, this weekend they decided that Agustín can only choose values that are powers of 2 (i.e., values $$$x$$$ for which there exists a non-negative integer $$$k$$$ such that $$$x = 2^k$$$, such as $$$1$$$, $$$2$$$, $$$4$$$, $$$8, \dots$$$, etc.) and Brian can only choose odd values.

To avoid always playing with the same numbers, they play $$$Q$$$ games, each with a list of numbers generated from an original list of $$$N$$$ values $$$A_1, A_2, \dots A_N$$$. Each game is described with two numbers $$$L$$$ and $$$R$$$, and is played with the list of numbers that are between positions $$$L$$$ and $$$R$$$ of the original list, that is $$$A_{L}, A_{L+1}, \dots, A_{R}$$$ (including both extreme positions).

Given the $$$N$$$ values of the original list $$$A_1$$$, $$$A_2$$$, $$$\dots$$$, $$$A_N$$$ and the description of the $$$Q$$$ games, decide what the result will be for each of the $$$Q$$$ games if Agustín and Brian play optimally.

Input

A line with two values $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 2\cdot 10^5)$$$, which denote the length of the list and the number of games to be played, respectively.

A line with the $$$N$$$ values $$$A_i$$$ of the original list $$$(1 \leq A_i \leq 10^4)$$$.

Finally, there are $$$Q$$$ lines that describe the games. Each line describes a game with two values $$$L$$$ and $$$R$$$ $$$(1 \leq L \leq R \leq N)$$$ that denote that this game uses the values $$$A_{L}, A_{L+1}, \dots, A_{R}$$$ from the original list.

Output

$$$Q$$$ lines, where the $$$j$$$-th line denotes the result of the $$$j$$$-th game, which should be "A", "B" or "E" according to whether Agustín, Brian, or the game ends in a tie, respectively, when played optimally.

Example
Input
8 3
4 2 2 2 3 3 1 6
1 3
2 6
5 8
Output
A
E
B
Note

In the first game of the example, they play with the list $$$[4, 2, 2]$$$. Playing optimally, Agustín manages to get all the numbers, and therefore Agustín wins the first game.