XOR
Nazar has a favorite number k and an array a[i] of length n. He needs your help to answer m queries.
For each query, specified by a pair of numbers l and r, your task is to determine the number of pairs of integers i and j such that l ≤ i ≤ j ≤ r and the xor (represented by the symbol ^ in C++) of the numbers a[i], a[i+1], ..., a[j] equals k.
Input
The first line contains three integers n, m, and k (where 1 ≤ n, m ≤ 10^5 and 0 ≤ k ≤ 10^6) — representing the length of the array, the number of queries, and Nazar's favorite number, respectively.
The second line contains n integers a[i] (where 0 ≤ a[i] ≤ 10^6) — Nazar's array. The following m lines each contain two integers l[i] and r[i] (where 1 ≤ l[i], r[i] ≤ n), which define the i-th query.
Output
Output m lines, each containing the answer to the corresponding query.