Bititehete avaldis

문제

Janika õppis hiljuti bititehete AND, OR ja XOR kohta ning tahab nüüd nendega avaldise koostada ja selle väärtust arvutada.

Avaldise algusesse kirjutab Janika arvu $00$. Selle järele kirjutab ta $NN$ tehet, kus iga tehe kasutab ühte õpitud bitioperatsiooni ning mingisugust täisarvu, näiteks "AND 5". Seega võib ta $N=6N\; =\; 6$ korral saada tulemuseks näiteks avaldise

0 XOR 2 AND 5 OR 9 XOR 0 AND 8 OR 10.

Avaldise väärtust arvutab ta alati vasakult paremale, nagu selles oleks mõttelised sulud järgmiselt

((((((0 XOR 2) AND 5) OR 9) XOR 0) AND 8) OR 10).

Edasi tahab Janika hakata oma avaldises üksikuid tehteid muutma, näiteks võib ta "OR 9" asemele kirjutada "XOR 13". Ta teeb oma avaldises üksteise järel $QQ$ muudatust ja tahab iga muudatuse järel teada sellega saadud uue avaldise väärtust.

입력

Sisendi esimesel real on kaks täisarvu: avaldise tehete arv $NN$ ($1\le N\le {10}^{5}1\; \backslash le\; N\; \backslash le\; 10^5$) ja muudatuste arv $QQ$ ($1\le Q\le {10}^{5}1\; \backslash le\; Q\; \backslash le\; 10^5$).

Järgmisel $NN$ real on igaühel algse avaldise ühe tehte kirjeldus: tehte nimi AND, OR või XOR ja täisarv $XX$ ($0\le X\le {10}^{9}0\; \backslash le\; X\; \backslash le\; 10^9$).

Järgmisel $QQ$ real on igaühel ühe muudatuse kirjeldus: asendatava tehte järjekorranumber $II$ ($1\le I\le N1\; \backslash le\; I\; \backslash le\; N$) ning uue tehte nimi AND, OR või XOR ja uus täisarv $XX$ ($0\le X\le {10}^{9}0\; \backslash le\; X\; \backslash le\; 10^9$).

출력

Iga muudatuse kohta väljasta eraldi reale üks täisarv: avaldise väärtus selle muudatuse järel.

힌트

AND ("loogiline JA") on loogiline tehe kahe tõeväärtuse vahel, mille tulemus on "tõene", kui mõlema operandi väärtus on "tõene", ja "väär" igal muul juhul. OR ("loogiline VÕI") tulemus on "väär", kui mõlema operandi väärtus on "väär", ja "tõene" igal muul juhul. XOR ("välistav VÕI") tulemus on "tõene", kui täpselt üks operandidest "tõene", ja "väär" igal muul juhul.

Nende tehete rakendamisel arvudele vaadatakse arvude esitust kahendsüsteemis, tõlgendatakse iga bitti tõeväärtusena ($11$ = "tõene", $00$ = "väär"), rakendatakse tehe operandide kohakuti olevatele bittidele (ühelised omavahel, kahelised omavahel j.n.e) ning koostatakse saadud tulemustest uus kahendarv.

Näiteks arvu $55$ kahendkuju on ${0101}_{2}0101\_2$ ja arvu $1212$ kahendkuju ${1100}_{2}1100\_2$. Avaldise ${0101}_{2}0101\_2$ XOR ${1100}_{2}1100\_2$ väärtuse kahendkuju arvutatakse järgmiselt: ühelised $11$ XOR $0=10\; =\; 1$; kahelised $00$ XOR $0=00\; =\; 0$; neljalised $11$ XOR $1=01\; =\; 0$; kaheksalised $00$ XOR $1=11\; =\; 1$. Kokku saame seega ${0101}_{2}0101\_2$ XOR ${1100}_2={1001}_{2}1100\_2\; =\; 1001\_2$, mis on arvu $99$ kahendkuju. Seega $55$ XOR $12=912\; =\; 9$.

4 3
XOR 2
OR 5
OR 9
XOR 0
2 AND 5
3 OR 8
4 XOR 10

9
8
2