Module: Mo algorithm

Problem

Evan has a favorite number k and an array a_i of length n. Now it asks you to answer m requests.

For each query given by a pair of numbers l and r, it is required to find the number of pairs of integers i and j such that l ≤ i ≤ j ≤ r and xor of numbers a_i , a_i + 1, ..., a_j is k.

Input:
The first line contains integers n, m and k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤  10⁶) — the length of the array, the number of requests, and Evan's favorite number, respectively.
The second line contains n integers ai (0 ≤ a_i ≤ 10⁶) — Evan's array.
Then there are m lines. The i-th line contains numbers l_i and r_i (1 ≤ l_i ≤ r< sub>i ≤ n) defining the i-th query.

Output:
Print m lines, the answers to the questions in the order they appear in the input.

Examples:
 

Input	Output
6 2 3 1 2 1 1 0 3 16 3 5	7 0
5 3 1 1 1 1 1 1 15 24 1 3	9 4 4