8. Akademické zbrane

Po desiatkach rokov a nespočetných nociach strávených v observatóriu sa mu to konečne podarilo! Bc. et Mgr. et Mudr. et PhDr Peťo Phd. Etc. Csc. konečne objavil planétku. Rozhodol sa ju nazvať KSP-8. A teraz zostáva už len jediné – postaviť raketu a prežiť zvyšok svojho života na vysnívanej planéte. Ale ako na to? Potreboval by poradiť od niekoho, kto má veľa skúseností s lietaním…

Taylor Swift je znova po mnohých rokoch na turné! Swifties vískajú, hateri hateujú a lístky sa míňajú. S novým turné však prichádza aj ďalšia novinka - každý, kto si zakúpi VIP lístok, získa osobne od Taylor radu do života.

Nie všetky Taylorine rady sú však rovnocenné. Napríklad dostať rovnakú radu dvakrát je samozrejme zbytočné. Ktoré lístky si má Peťo kúpiť, aby uspel na svojej misii?

Úloha

Taylor Swift má naplánovaných \(n\) koncertov. Každý z nich je popísaný dvoma číslami \(a_i, b_i; a_i \leq b_i\). Na každom koncerte, ktorého sa Peťo zúčastní dostane Taylorinu radu - ľubovoľné číslo od \(a_i\) do \(b_i\) vrátane. Kvalita jeho rakety potom bude rovná bitovému OR-u všetkých rád, ktoré získal.

Postupne dostávate \(q\) queries. Queries majú 2 typy:

• Zmenili sa parametre jedného koncertu.
• Aká je maximálna možná kvalita rakety pri navštívení koncertov \(l\) až \(r\) vrátane?

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 3 \cdot 10^5\)) udávajúce počet koncertov, ktoré Taylor plánuje.

Na každom z nasledujúcich \(n\) riadkov sa nachádzajú čísla \(a_i\) a \(b_i\) (\(0 \leq a_i \leq b_i \leq 10^9\)) popisujúce i-ty koncert.

Na ďaľšom riadku sa nachádza číslo \(q\) (\(1 \leq q \leq 3 \cdot 10^5\)) – počet queries.

Každý zo zvyšných \(q\) riadkov popisuje jednu query:

• u {i} {a} {b} (\(1 \leq i \leq n\)) – Parametre i-teho koncertu sa zmenili na \(a,b\).
• q {l} {r} (\(1 \leq l \leq r \leq n\)) – Aká je maximálna možná kvalita rakety pri navštívení koncertov \(l\) až \(r\) vrátane?

Hodnotenie

Úloha má 4 sady vstupov. V prvých troch platia navyše obmedzenia:

• V prvej sade platí \(n, q \leq 5000\).
• V druhej sade sú všetky query typu q – teda nie sú tu žiadne updaty.
• V tretej sade pre každé \(i\) platí \(a_i == 0\), a to aj po updateoch.

Formát výstupu

Na každú query typu q odpovedajte vypísaním jediného čísla na samostatný riadok - maximálnou možnou kvalitou rakety.

Príklad

Input:

3
1 2
0 1
3 5
4
q 1 2
q 2 3
u 2 0 2
q 2 3

Output:

3
5
7

Pri prvej query zoberieme na prvom koncerte radu \(2\) a na druhom \(1\), a \(2 \operatorname{OR} 1 = 3\). Pri druhej zoberieme \(5\) a \(1\). V prípade poslednej query už vieme na druhom koncerte zobrať aj dvojku, teda dostávame \(2 \operatorname{OR} 5 = 7\).