Massivlə oyun#11266
Lagera çatdıqdan sonra, Manni və Sid orada ədədlərdən ibarət bir sıra tapdılar. Onlar bu sıradan istifadə edərək bir oyun oynamaq qərarına gəldilər. Oyunda müəyyən bir qaydada sıraya yaxınlaşaraq onunla əməliyyatlar aparacaqlar.
Manni sıraya yaxınlaşdıqda, o, sıranın bir elementinin dəyərini istənilən başqa bir dəyərə dəyişə bilər. Sid sıraya yaxınlaşdıqda isə, o, iki ədəd a və b (1 ≤ a ≤ b ≤ n) seçir. Sonra, bütün mümkün l və r üçün, elə ki, a ≤ l ≤ r ≤ b, o, l-dən r-ə qədər olan (daxil olmaqla) sıranın alt hissəsini götürəcək, onun elementlərinin xor-unu (bitwise məntiqi və ya) hesablayacaq və alınan bütün ədədlərin cəmini tapacaq.
Lakin, dostların yola davam etməsi lazımdır və onların oyun oynamağa vaxtları yoxdur. Hamıya məlum olduğu kimi, mamontların mükəmməl yaddaşı var. Buna görə də, Manni tapdıqları sıranı və oyunda etməyi planlaşdırdıqları bütün gedişləri yadda saxladı və yolda bu oyunu oynamağa qərar verdi. Ona Sidin gedişlərində hansı ədədləri alacağını müəyyən etməyə kömək edin.
Birinci sətirdə iki tam ədəd n və m (1 ≤ n, m ≤ 10^5) - sıranın uzunluğu və oyundakı gedişlərin sayı verilir. Növbəti sətirdə n tam ədəd v[i] (0 ≤ v[i] ≤ 10^8) - başlanğıc sıra verilir.
Növbəti m sətirdə üç ədəd - gedişlərin təsviri verilir.
1 i x - Manni i nömrəli elementin dəyərini x-ə dəyişdi (1 ≤ i ≤ n, 0 ≤ x ≤ 10^8).
2 a b - Sid a və b ədədlərini seçdi (1 ≤ a ≤ b ≤ n).
Sidin hər gedişi üçün alınan cəmi yeni sətirdə çıxarın.
Nümunə 1