D. Мишка ба сонирхолтой нийлбэр

хугацааны хязгаарлалт 3.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Мишка програмчлалд дуртай. Саяхан түүний төрсөн өдөр болж өнгөрсөн учир түүний найзууд түүнд $n$ элементтэй эерэг бүхэл тоон $a_{1}, a_{2}, ..., a_{n}$ массив бэлэглэхээр шийдсэн!

Мишка массивтаа дуртай болсон ба шууд массивийн гоо үзэсгэлэнгийн утгыг тодорхойлохоор шийдсэн боловч тэр балчир ба том массивуудыг боловсруулж чадахгүй. Ийм учраас тэр таныг түүн дээр зочилж $m$ асуулга боловсруулахыг урьж байна.

Асуулга бүрийг дараах аргаар боловсруулна:

  1. $l$ ба $r$ ($1 ≤ l ≤ r ≤ n$) хоёр тоог тодорхойлох ба эдгээр нь асуулгын сегментийн хүрээ юм.
  2. Массивийн $[l,  r]$ сегментэд байгаа тэгш тоо бүхий давталттай бүхэл тоонуудыг ($a_{l}, a_{l + 1}, ..., a_{r}$ дараалал дахь бүхэл тоонууд) бичнэ.
  3. Бичсэн бүхэл тоонуудын XOR нийлбэрийг олох ба энэ нь асуулгын хариу юм. Тодорхой хэлбэл хэрвээ бичигдсэн хоёртын тооллын системийн $x_{1}, x_{2}, ..., x_{k}$ тоонууд байна гэвэл Мишка утгыг мэдэхийг хүсч байгаа ба энд нь логик XOR үйлдлийг илэрхийлнэ.

Бяцхан баавгайнууд л массивийн гоо үзэсгэлэн гэж мэддэг учир таны хийх зүйл бол асуулга бүрт хариулах юм.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 1 000 000$) байх буюу массивийн элементүүдийн тоо юм.

Оролтын хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) байх буюу массивийн элементүүд юм.

Оролтын гурав дахь мөрөнд бүхэл тоо $m$ ($1 ≤ m ≤ 1 000 000$) байх ба асуулгуудын тоо юм.

Дараагийн $m$ мөр бүрт харгалзах асуулгыг $l$ ба $r$ ($1 ≤ l ≤ r ≤ n$) хос бүхэл тоогоор илэрхийлэх ба эдгээр нь сегментийн хүрээ юм.

Гаралт

Асуулгуудын хариуг оролтонд өгсөн дарааллаар нь хэвлэх буюу $m$ эерэг бүхэл тоо хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3
3 7 8
1
1 3
Гаралт
0
Оролт
7
1 2 1 3 3 2 3
5
4 7
4 5
1 3
1 7
1 5
Гаралт
0
3
1
3
2

Тэмдэглэл

Хоёр дахь жишээн дээр:

Эхний асуулгын сегментэд тэгш удаа давтагдсан ямар ч тоо байхгүй тиймээс хариу $0$ байна.

Хоёр дахь асуулга дээр зөвхөн $3$ л тэгш удаа давтагдсан учир хариу $3$ байна.

Гурав дахь асуулга дээр зөвхөн бүхэл тоо $1$ л бичигдэх ба хариулт $1$ байна.

Дөрөв дахь асуулга дээр массивийн бүх элементүүдийг авч үзнэ. Зөвхөн $1$ ба $2$ нь л тэгш удаа давтагдсан байна. Ингээд хариулт байна.

Тав дахь асуулга дээр $1$ ба $3$-г бичих ба хариулт нь .

Сэтгэгдлүүдийг ачааллаж байна...