Given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$, and given query parameters $l$ and $r$, find how many subsegments within the range $a_l, a_{l+1}, \dots, a_r$ have an XOR sum equal to $k$. That is, for all pairs $x, y$ such that $l \le x \le y \le r$, how many pairs $(x, y)$ satisfy $a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k$.

Input

The first line contains three integers $n, m, k$. The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$. The next $m$ lines each contain two integers $l_j, r_j$, representing one query.

Output

Output $m$ lines, each containing the result for the corresponding query.

Examples

Input 1

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

Output 1

4
2
1
2
1

Constraints

• For 30% of the data, $1 \le n, m \le 1000$.
• For 100% of the data, $1 \le n, m \le 10^5$, $0 \le k, a_i \le 10^5$, $1 \le l_j \le r_j \le n$.