Боб-д дуртай тоо нь болох $k$ болон $n$ урт бүхий $a_{i}$-үүдийн цуваа байжээ.Одоо тэрээр таныг $m$ ширхэг асуултад хариулахыг хүсэв.Асуулт бүр хос $l_{i}$ болон $r_{i}$-аар өгөгдөх ба таныг $l ≤ i ≤ j ≤ r$ болон $a_{i}, a_{i + 1}, ..., a_{j}$ тоонуудын XOR нь $k$-тай тэнцүү байх гэсэн 2 нөхцөлийг хангах хэчнээн ширхэг бүхэл тоон $i$ болон $j$ хосууд байгааг тоолохыг хүсжээ.

Оролт

Эхний мөрөнд харгалзан цувааны урт,асуултын тоо,Боб-ын дуртай тоог илэрхийлэх бүхэл тоонууд $n$, $m$ болон $k$ ($1 ≤ n, m ≤ 100 000$, $0 ≤ k ≤ 1 000 000$) өгөгдөнө.

2-дахь мөрөнд Боб-ын цуваа болох $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ 1 000 000$) өгөгдөнө.

Үүний дараах $m$ ширхэг мөрний $i$-дахь мөрөнд $i$-дахь асуултын параметрүүд болох $l_{i}$ болон $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө.

Гаралт

Оролтод өгөгдсөн дарааллаар асуулт болгоны хариултыг $m$ ширхэг мөрөнд хэвлэнэ.

Эхний жишээний эхний асуултад тохирох хосууд нь ($1$, $2$), ($1$, $4$), ($1$, $5$), ($2$, $3$), ($3$, $6$), ($5$, $6$), ($6$, $6$) байх ба 2-дахь асуултад тохирох хос байхгүй байна

2-дахь жишээнд сондгой урт бүхий бүх дэд цуваануудын XOR нь $1$-тэй тэнцүү байна.