## DMPG '16 G6 - SAO Queries

View as PDF

Points: 30 (partial)
Time limit: 3.5s
Memory limit: 768M

Author:
Problem types

Kirito has an array of size , indexed from to . There are queries he wants you to perform on this array. Each query is a Squared Appearances Online (SAO) query on a subarray of the array. The SAO query is computed as follows: for each element in the subarray, let be the number of occurrences of in the subarray. The result of the SAO query is the sum of for each in the subarray when taken modulo (if an element appears more than once in the array, you should add for each time it appears in the array).

You may think that this problem is pretty easy so far, but remember the 'O' in SAO query: you should perform these queries in an online manner. To enforce this condition, the input will be encrypted (see the input specification for more details).

#### Input Specification

The first line of input will contain and .
The second line of input will contain space separated nonnegative integers, the elements of the array.
The next lines of input will each contain a encrypted query pair : you should decode them by finding and , where is the answer to the previous query (or 0 if it's the first query). Then you should output the result of the SAO query on the subarray from to inclusive (0-based index). denotes the bitwise XOR operation. It is guaranteed that and will represent a valid subarray after decryption.

#### Output Specification

For each SAO query, output the result on a new line. Remember that the result should be taken modulo and that will be equal to exactly the value you printed last (so, it will also be between and ).

#### Constraints

All other integers in the input will be between and , inclusive.

#### Sample Input

5 5
0 1 2 1 2
0 4
9 10
7 5
7 1
6 1

#### Sample Input (not encrypted)

For your convenience, we provide a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).

5 5
0 1 2 1 2
0 4
0 3
1 3
2 4
3 4

#### Sample Output

9
6
5
5
2