Subarray XOR Query

Given an integer sequence \(a_1,a_2,\dots,a_n\) of length \(n\) and a query defined by two indices \(l\) and \(r\), your task is to count the number of subarrays within the segment \(a_l,a_{l+1},\dots,a_r\) whose XOR sum equals \(k\). In other words, for all pairs \((x,y)\) with \(l \le x \le y \le r\), you need to count how many satisfy

\[ a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k \]

Note: The operator \(\oplus\) denotes the bitwise XOR.

inputFormat

The first line contains three integers: \(n\) (the length of the array), \(q\) (the number of queries), and \(k\) (the target XOR value).

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

Each of the following \(q\) lines contains two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output a single line containing one integer: the number of subarrays within the range \([l, r]\) whose XOR sum equals \(k\).

sample

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

3
1
1