You are given a sequence of $n$ positive integers $a$ and a constant $x$.

Define $x \oplus y$ as the bitwise XOR of $x$ and $y$.

There are $q$ queries. Each query provides a range $[l, r]$, and you need to find the number of pairs $(i, j)$ in this range such that $i < j$ and $(a_i \oplus a_j) \le x$.

Input

The first line contains two positive integers $n$ and $x$, representing the length of the sequence and the given constant, respectively.

The next line contains $n$ integers representing the sequence $a$.

The third line contains a positive integer $q$, representing the number of queries.

The following $q$ lines each contain two positive integers $l$ and $r$, representing a query.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

11 4
11 4 5 1 4 1 9 1 9 8 10
5
1 4
1 9
1 9
8 10
8 10

Output 1

2
12
12
1
1

Subtasks

Idea: Dpair, Solution: Dpair, Code: Dpair, Data: Dpair & nzhtl1477

For $1\%$ of the data, it is the sample case.

For another $19\%$ of the data, $n, q \le 100$.

For another $19\%$ of the data, $n, q \le 1000$.

For another $19\%$ of the data, $q \le 100$.

For another $19\%$ of the data, $a_i, x \le 100$.

For $100\%$ of the data, $1 \le n, a_i, x \le 2\times 10^5, 1 \le q \le 10^6$.