Problem Description

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

Let $x \oplus y$ denote the bitwise XOR of $x$ and $y$.

There are $q$ queries. Each query gives an interval $[l, r]$. You need to find how many pairs $(i, j)$ in this interval satisfy $i < j \land (a_i \oplus a_j) \le x$.

Input Format

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

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

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

The next $q$ lines each contain two positive integers $l, r$, representing one query.

Output Format

Output $q$ lines. Each line contains one integer, representing the answer.

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

2
12
12
1
1

Hint

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

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

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

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

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

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

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

Translated by ChatGPT 5