Đoạn Con XOR Bằng K

Cho dãy $a$ và số nguyên $K$. Với mỗi đoạn đóng $[l,r]$, hãy đếm số cặp chỉ số $i,j$ thỏa $l\le i\le j\le r$ và $a_i\mathrm{xor}{a}_{i+1}\mathrm{xor}\cdots \mathrm{xor}{a}_j=K$.

Input

• Dòng đầu chứa $n,q$ và $K$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,\dots ,a_n$.
• Mỗi trong $q$ dòng tiếp theo chứa $l$ $r$.

Output

• In số đoạn con hợp lệ của mỗi truy vấn trên một dòng.

Constraints

• $1\le n,q\le 10^5$.
• $0\le K,a_i<2^{20}$.
• $1\le l\le r\le n$.
• Đáp án vừa kiểu số nguyên $64$ bit có dấu.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

4
2
2
1