已知一个长度为 $n$ 的整数数列 $a_1,a_2,…,a_n$，给定查询参数 $l、r$，问在 $[l,r]$ 区间内，有多少连续子序列满足异或和等于 $k$。

也就是说，对于所有的 $x,y(l \le x \le y \le r)$，能够满足 $a_x \oplus a_{x+1} \oplus … \oplus a_y = k$ 的 $x,y$ 有多少组。

输入格式

第一行，为 $3$ 个整数 $n,m,k$。

第二行为空格分开的 $n$ 个整数，即 $a_1,a_2,…,a_n$。

接下来 $m$ 行，每行两个整数 $l_j,r_j$，表示一次查询。

输出格式

输出共 $m$ 行，对应每个查询的计算结果。

数据范围

$1 \le n,m \le 10^5$,
$0 \le k,a_i \le 10^5$,
$1 \le l_j \le r_j \le n$

输入样例：

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

输出样例：

4
2
1
2
1