Preparing NOJ

Bob has a favorite number *k* and *a*_{i} of length *n*. Now he asks you to answer *m* queries. Each query is given by a pair *l*_{i} and *r*_{i} and asks you to count the number of pairs of integers *i* and *j*, such that *l* ≤ *i* ≤ *j* ≤ *r* and the xor of the numbers *a*_{i}, *a*_{i + 1}, ..., *a*_{j} is equal to *k*.

The first line of the input contains integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 100 000, 0 ≤ *k* ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.

The second line contains *n* integers *a*_{i} (0 ≤ *a*_{i} ≤ 1 000 000) — Bob's array.

Then *m* lines follow. The *i*-th line contains integers *l*_{i} and *r*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*) — the parameters of the *i*-th query.

Print *m* lines, answer the queries in the order they appear in the input.

6 2 3

1 2 1 1 0 3

1 6

3 5

7

0

5 3 1

1 1 1 1 1

1 5

2 4

1 3

9

4

4

In the first sample the suitable pairs of *i* and *j* for the first query are: (1, 2), (1, 4), (1, 5), (2, 3), (3, 6), (5, 6), (6, 6). Not a single of these pairs is suitable for the second query.

In the second sample xor equals 1 for all subarrays of an odd length.

Info

Provider CodeForces

Origin Codeforces Round #340 (Div. 2)

Code CF617E

Tags

data structures

Submitted 37

Passed 12

AC Rate 32.43%

Date 03/04/2019 15:05:37

Related