给你一个长度为 $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$ 。