長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ と整数 $K$ が与えられる。以下のクエリを処理するプログラムを作成せよ。

• l r: $l \le i \le j \le r$ かつ $A_i, A_{i+1}, \ldots, A_j$ の XOR が $K$ に等しいような組 $(i, j)$ の個数を出力せよ。

入力

最初の行には 2 つの整数 $N$ $(1 \le N \le 100{,}000)$ と $K$ $(0 \le K \le 1{,}000{,}000)$ が含まれる。

2 行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ が含まれる。$(0 \le A_i \le 1{,}000{,}000)$

3 行目には整数 $M$ $(1 \le M \le 100{,}000)$ が含まれ、これはクエリの数を表す。

次の $M$ 行にはそれぞれ 2 つの整数 $l, r$ が含まれ、クエリを表す。$(1 \le l \le r \le N)$

出力

各クエリに対して、答えを表す整数を一行に出力せよ。

入出力例

入力例 1

6 3
1 2 1 1 0 3
2
1 6
3 5

出力例 1

7
0

入力例 2

5 1
1 1 1 1 1
3
1 5
2 4
1 3

出力例 2

9
4
4