Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$ và một số nguyên $K$. Hãy viết chương trình xử lý các truy vấn sau:

• l r: in ra số lượng cặp $(i, j)$ sao cho $l \le i \le j \le r$ và XOR của $A_i, A_{i+1}, \ldots, A_j$ bằng $K$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ $(1 \le N \le 100{,}000)$ và $K$ $(0 \le K \le 1{,}000{,}000)$.

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$. $(0 \le A_i \le 1{,}000{,}000)$

Dòng thứ ba chứa một số nguyên $M$ $(1 \le M \le 100{,}000)$, số lượng truy vấn.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l, r$, mô tả một truy vấn. $(1 \le l \le r \le N)$

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa một số nguyên duy nhất là kết quả.

Ví dụ

Đầu vào 1

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

Đầu ra 1

7
0

Đầu vào 2

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

Đầu ra 2

9
4
4