e-olymp
Yarışlar

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

XOR-layan Murad

Murad XOR-lamağı çox xoşlayır. O bütün günü dayanmadan ədədləri bir-biri ilə XOR-layır.

Bu dəfə Murad belə bir məsələ ilə qarşılaşdı: Ona n ölçülü a massivi verilir. O, bu massivin üzərində q sayda sorğu icra etməlidir. Sorğular aşağıdakı kimi iki növdə ola bilər:

1) 1 l r - bu növ sorğuda l, r (1l < rn) aralığında olan bütün cütlərin XOR-ları cəmini, yəni,

xorimg.png cəmini tapmaq tələb olunur.

2) 2 l r v - bu növ sorğuda massivin l, r (1lrn) aralığında olan bütün elementlərini v ilə XOR-lamaq tələb olunur.

Qeyd: Burada XOR məntiqi xor əməliyyatını göstərir.

Giriş verilənləri

İlk sətirdə iki tam ədəd nq (2n2 * 105, 1q105) - uyğun olaraq a massivinin ölçüsü və sorğuların sayı, ikinci sətirdə isə n sayda tam ədəd a massivinin elemetləri (0ai109) verilir.

Növbəti q sətrin hər birində bir sorğu verilir. i-ci sorğuda, öncə sorğunun növünü göstərən 1 və ya 2 ədədi verilir. Əgər 1-ci növ sorğu olarsa, daha sonra iki tam ədəd liri (1li < rin), əks halda üç tam ədəd li, rivi (1lirin, 0vi109) verilir.

Çıxış verilənləri

Çıxışa 1-ci növ sorğulara uyğun cavabları, hər birini yeni sətirdə olmaqla verin.

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 3
1 2 3
1 1 3
2 1 3 2
1 1 2
Çıxış verilənləri #1
6
3
Giriş verilənləri #2
4 6
4 8 7 8
1 2 4
2 1 2 2
1 3 4
2 1 1 8
1 1 3
1 1 4
Çıxış verilənləri #2
30
15
26
49
Müəllif Rashad Mammadov
Mənbə İOİ 2019 Azərbaycan komandasına seçim turu