Chips on a Board
Contest: Educational Codeforces Round 107 (Rated for Div. 2)
Difficulty rating: 2700
Tags: bitmasks, brute force, data structures, dp, games, two pointers

Alice and Bob have a rectangular board consisting of $$$n$$$ rows and $$$m$$$ columns. Each row contains exactly one chip.

Alice and Bob play the following game. They choose two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le m$$$ and cut the board in such a way that only the part of it between column $$$l$$$ and column $$$r$$$ (inclusive) remains. So, all columns to the left of column $$$l$$$ and all columns to the right of column $$$r$$$ no longer belong to the board.

After cutting the board, they move chips on the remaining part of the board (the part from column $$$l$$$ to column $$$r$$$). They make alternating moves, and the player which cannot make a move loses the game. The first move is made by Alice, the second — by Bob, the third — by Alice, and so on. During their move, the player must choose one of the chips from the board and move it any positive number of cells to the left (so, if the chip was in column $$$i$$$, it can move to any column $$$j < i$$$, and the chips in the leftmost column cannot be chosen).

Alice and Bob have $$$q$$$ pairs of numbers $$$L_i$$$ and $$$R_i$$$. For each such pair, they want to determine who will be the winner of the game if $$$l = L_i$$$ and $$$r = R_i$$$. Note that these games should be considered independently (they don't affect the state of the board for the next games), and both Alice and Bob play optimally.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of rows and columns on the board, respectively.

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le m$$$), where $$$c_i$$$ is the index of the column where the chip in the $$$i$$$-th row is located (so, the chip in the $$$i$$$-th row is in the $$$c_i$$$-th column).

The third line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$).

Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \le L_i \le R_i \le m$$$).

Output format:
Print a string of $$$q$$$ characters. The $$$i$$$-th character should be A if Alice wins the game with $$$l = L_i$$$ and $$$r = R_i$$$, or B if Bob wins it.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
8 10
1 3 3 7 4 2 6 9
7
2 3
1 3
1 4
1 10
5 10
8 10
9 10

Example output:
BAAAAAB

Editorial:
The model solution is $$$O(N \sqrt{N \log N})$$$, where $$$N = \max(n, m, q)$$$, but it seems that there are faster ones. I'll explain the model solution nevertheless.
It's easy to see (using simple Nim theory) that the answer for a query $$$i$$$ is B iff the xor of $$$c_j - L_i$$$ for all chips such that $$$L_i \le c_j \le R_i$$$ is equal to $$$0$$$. Let's calculate this xor for every query. This number contains at most $$$18$$$ bits, and we will process these bits differently: we will choose some number $$$K$$$ and use one solution to calculate $$$K$$$ lowest bits, and another solution to compute $$$18 - K$$$ highest bits. One idea is common in both solutions: we split each query into two queries — a query $$$(L_i, R_i)$$$ can be represented as a combination of two queries $$$Q(L_i, L_i)$$$ and $$$Q(R_i + 1, L_i)$$$, where $$$Q(x, y)$$$ is the xor of all numbers $$$c_j - y$$$ such that $$$c_j \ge x$$$. After converting the queries, for every $$$x \in [1, m]$$$, store each query of the form $$$Q(x, y)$$$ in some sort of vector (or any other data structure). We will use an approach similar to sweep line: iterate on $$$x$$$ and solve the queries for the current $$$x$$$. These ideas will be used both for the solution calculating $$$K$$$ lowest bits and for the solution calculating $$$18 - K$$$ highest bits.
How to find $$$K$$$ lowest bits in each query? Iterate on $$$x$$$ from $$$m$$$ to $$$1$$$ and maintain the number of occurrences of each number $$$c_i$$$ we met so far. Then, at a moment we want to calculate $$$Q(x, y)$$$, simply iterate on all of the values of $$$c_i$$$ and process each value in $$$O(1)$$$ (if the number of occurrences of some value $$$z$$$ is odd, update the current answer to the query by xoring the number with $$$z - y$$$, otherwise just skip it). And since we are interested only in $$$K$$$ lowest bits, for each $$$c_i$$$, we need only the remainder $$$c_i \mod 2^K$$$, so the number of different values is $$$O(2^K)$$$. Thus, this part of the solution runs in $$$O(n + m + 2^Kq)$$$.
Okay, what about $$$18 - K$$$ highest bits in each query? We can see that, for every number $$$c_i$$$, the highest bits of $$$c_i - x$$$ don't change too often when we iterate on $$$x$$$: there will be about $$$\frac{m}{2^K}$$$ segments where the highest bits of $$$c_i - x$$$ have different values. We can build a data structure that allows use to process two queries: xor all numbers on a segment with some value and get the value in some position (Fenwick trees and segment trees can do it). Then, we again iterate on $$$x$$$ from $$$m$$$ to $$$1$$$. When we want to process a number $$$c_i$$$, we find the segments where the highest bits of $$$c_i - x$$$ have the same value and perform updates on these segments in our data structure. When we process a query of the form $$$Q(x, y)$$$, we simply get the value in the position $$$y$$$ from our data structure. This part of the solution works in $$$O(n \frac{m}{2^K} \log m + m + q)$$$.
By choosing $$$K$$$ optimally, we can combine these two parts into a solution with complexity of $$$O(N \sqrt{N \log N})$$$.