Cho mảng \(a\) gồm \(n\) số nguyên và số \(k\). Mỗi truy vấn \((l,r)\) yêu cầu đếm các cặp \(i,j\) thỏa \(l\le i\le j\le r\) và \(a_i\oplus a_{i+1}\oplus\cdots\oplus a_j=k\), trong đó \(\oplus\) là phép XOR theo bit.

Dữ liệu vào

• Dòng đầu chứa \(n,m,k\).
• Dòng tiếp theo chứa \(n\) số \(a_1,\ldots,a_n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(l,r\) của một truy vấn.

Dữ liệu ra

In \(m\) dòng, mỗi dòng là đáp án của một truy vấn theo thứ tự nhập.

Ràng buộc

• \(1\le n,m\le100\,000\).
• \(0\le k,a_i\le1\,000\,000\).
• \(1\le l\le r\le n\).

Ví dụ

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

7
0

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

9
4
4

Nguồn

Codeforces 617E - XOR và số yêu thích.