move is made by Alice, the second — by Bob, the third — by Alice, etc. During their turn, the player should pick one of the chips from the board and move it any sure number of cells to one side (along these lines, if the chip was in segment I, it can move to any segment j
Correct answer will be upvoted else downvoted. Computer science.
first move is made by Alice, the second — by Bob, the third — by Alice, etc. During their turn, the player should pick one of the chips from the board and move it any sure number of cells to one side (along these lines, if the chip was in segment I, it can move to any segment j<i, and the chips in the furthest left segment can't be picked).
Alice and Bob have q sets of numbers Li and Ri. For each such pair, they need to figure out who will be the victor of the game if l=Li and r=Ri. Note that these games ought to be thought about freely (they don't influence the condition of the board for the following games), and both Alice and Bob play ideally.
Input
The main line contains two integers n and m (1≤n,m≤2⋅105) — the number of lines and segments on the board, separately.
The subsequent line contains n integers c1,c2,… ,cn (1≤ci≤m), where ci is the file of the segment where the chip in the I-th line is found (in this way, the chip in the I-th line is in the ci-th segment).
The third line contains one integer q (1≤q≤2⋅105).
Then, at that point, q lines follow, the I-th of them contains two integers Li and Ri (1≤Li≤Ri≤m).
Output
Print a line of q characters. The I-th character ought to be An if Alice dominates the match with l=Li and r=Ri, or B if Bob wins it.
Step by step
Solved in 3 steps with 1 images
