给你一个长度为 $n$ 的正整数序列 $a$，和一个常数 $x$ 。
定义 $x \oplus y$ 表示 $x$ 异或 $y$。
有 $q$ 次询问，每次询问给出一段区间 $[l, r]$，问你这个区间中有多少二元组 $(i, j)$ 满足 $i < j \land (a_i \oplus a_j) \le x$。
输入格式
第一行两个正整数 $n, x$ ，分别表示序列长度和给定的常数。
后面一行 $n$ 个整数表示序列 $a$ 。
第三行一个正整数 $q$ 表示询问组数。
后面 $q$ 行，每行两个正整数 $l, r$ 表示一次询问。
输出格式
输出 $q$ 行，每行一个整数表示答案。
样例数据
样例输入
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子任务
Idea：Dpair，Solution：Dpair，Code：Dpair，Data：Dpair&nzhtl1477
对于 $1\%$ 的数据，为样例。
对于另外 $19\%$ 的数据，满足 $n,q\le 100$。
对于另外 $19\%$ 的数据，满足 $n,q\le 1000$。
对于另外 $19\%$ 的数据，满足 $q\le 100$。
对于另外 $19\%$ 的数据，满足 $a_i,x\le 100$。
对于 $100\%$ 的数据，满足 $1 \le n, a_i, x\le 2\times 10^5, 1 \le q \le 10^6$ 。