English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.

XOR and Favorite Number

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.

Input

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.

Output

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

Examples

Input

6 2 3
1 2 1 1 0 3
1 6
3 5

Output

7
0

Input

Output

9
4
4

Note

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.

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)