E. Завсар дахь XOR үйлдэл

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

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

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

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

Танд $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоонуудаас бүрдсэн $n$ элементтэй $a$ массив өгөгдөв. Энэ массив дээр дараах хоёр үйлдлийг хийхийг зөвшөөрдөг:

  1. Массивын $[l, r]$ завсар дахь элементүүдийн нийлбэрийг олно. Энэ нь $a_{l} + a_{l + 1} + ... + a_{r}$ нийлбэрийг олно гэсэн үг.
  2. Массивын $[l, r]$ завсар дахь элемент бүрийг $x$ тоотой xor үйлдлээр хувиргана. Энэ нь $a_l = a_l \oplus x,\ a_{l+1} = a_{l+1} \oplus x,\ ... ,\ a_r = a_r \oplus x$ үйлдлийг хийнэ гэсэн үг. Энэ үйлдлийг хийснээр массивын $r - l + 1$ элемент өөрчлөгдөнө.

$x \oplus y$ илэрхийлэл нь $x$ ба $y$ тоонуудын битийн xor үйлдлийг илэрхийлнэ. Өгөгдсөн үйлдэл нь орчин үеийн бүх програмчлалын хэлүүд дээр байдаг. Тухайлбал C++ болон Java хэлэнд "^" гэж тэмдэглэгддэг бол Pascal хэлэнд "xor" гэж тэмдэглэгддэг.

Танд дээр тодорхойлсон төрлийн $m$ ширхэг үйлдлүүдийн жагсаалт өгөгдсөн байна. Таны даалгавар бол өгөгдсөн бүх үйлдлүүдийг гүйцэтгээд, нийлбэр олох хүсэлт (1-р төрлийн) бүрийн хариуг хэвлэх юм.

Оролт

Эхний мөрөнд массивын хэмжээ болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо байна. Хоёр дахь мөрөнд массивын анхны элементүүд болох зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} ≤ 10^{6}$) бүхэл тоонууд байна.

Гурав дахь мөрөнд массив дээр гүйцэтгэх үйлдлүүдийн тоо болох $m$ ($1 ≤ m ≤  5 \cdot 10^{4}$) бүхэл тоо байна. Дараагийн $m$ мөрүүдийн $i$-р мөрийн эхэнд $t_{i}$ ($1 ≤ t_{i} ≤ 2$) бүхэл тоо байна. Энэ нь $i$-р хүсэлтийн төрлийг илэрхийлнэ. Хэрвээ $t_{i} = 1$ бол нийлбэрийг олох хүсэлт байна, харин $t_{i} = 2$ бол элементүүдийг өөрчлөх хүсэлт байна. $i$-р үйлдэл нь $1$-р төрлийн хүсэлт бол $t_{i}$-н араас $l_{i}, r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) хоёр бүхэл тоо байна. Хэрвээ $i$-р үйлдэл нь $2$-р төрлийн хүсэлт бол $t_{i}$-н араас $l_{i}, r_{i}, x_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n, 1 ≤ x_{i} ≤ 10^{6}$) гурван бүхэл тоо байна. Мөр бүр дэх тоонуудыг хооронд нь нэг зайгаар тусгаарлан бичнэ.

Гаралт

Нийлбэр олох хүсэлт бүрийн хариуг нэг нэг мөрөнд хэвлэнэ. Хариуг хэвлэхдээ хүсэлтүүдийн орсон дарааллаар хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

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

Оролт
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
Гаралт
26
22
0
34
11
Оролт
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
Гаралт
38
28
Сэтгэгдлүүдийг ачааллаж байна...