XOR#8277
Nazar has a favorite number and an array a_i of length . He needs your help to answer queries.
For each query, specified by a pair of numbers and , your task is to determine the number of pairs of integers and such that l \le i \le j \le r and the xor (represented by the symbol ^ in C++) of the numbers a_i, a_{i+1}, \ldots, a_j equals .
The first line contains three integers , , and (1 \le n, m \le 10^5; 0 \le k \le 10^6) — representing the length of the array, the number of queries, and Nazar's favorite number, respectively.
The second line contains integers a_i (0 \le a_i \le 10^6) — Nazar's array. The following lines each contain two integers l_i and r_i (1 \le l_i, r_i \le n), which define the -th query.
Output lines, each containing the answer to the corresponding query.
Example 1
Example 2