Mohit is a pro coder and likes to solve problems related to XOR. One day he saw his friend Naveen solving a problem related to XOR.

The problem is as follows:

Given an array A of n integers and a number k. In addition to that, you are given q queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the number of contiguous subarray [l,r] such that i ≤ l ≤ r ≤ j and bitwise XOR of elements from [l,r] is strictly less than k.

Mohit is busy solving the questions of Codebattle but also wants to submit the solution to the above problem before Naveen. Can you help him by solving the above problem.

To know about bitwise operators refer here.

Input

First line contains 3 integers n, q and k.

Next line consists of n integers denoting the elements of the array.

Next q lines consists of queries, each of the form i j.

Output

For each query, print a single line containing required output.

Constraints

1 <= n, q <= 3*10^4
0 <= A[i] <= 10^6
1 <= k <= 10^6
1 <= i, j <= n

30% score :
1 <= n, q <= 1000

100% score :
Original constraints