Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: bit_operations.in

Rezultatų failas: bit_operations.out

Jei norite pateikti savo sprendimą - prisijunkite.

BIT Operations

Domantas turi skaičių seką a sudarytą iš 2^n neneigiamų sveikųjų skaičių: a_1,a_2,...,a_{2^n}. Domantas nusprendė ant sekos išbandyti bitų operacijas ir sekai a apskaičiuoti skaičių v.

Apskaičiuojant skaičių v Domantui tenka atlikti kelias iteracijas. Pirmiausia jis susirašo naują seką a_1ORa_2,a_3ORa_4,...,a_{2^n-1}ORa_{2^n} sudarytą iš 2^{n-1} elementų. Sekančioje iteracijoje Domantas naudoja po pirmos iteracijos gautą skaičių seką ir vietoje bitų operacijos OR, taiko kitą - XOR operaciją ir gauna seką, sudarytą iš 2^{n-2} elementų. Trečioje iteracijoje jis vėl naudoja bitų operaciją OR ir taip kiekvienoje iteracijoje keičia operaciją iš OR į XOR ir atvirkščiai, kol galiausiai turi skaičių seką sudarytą tik iš 1 elemento, kuris ir yra skaičius v.

Pavyzdžiui turime seka a=(1,2,3,4). Surašius visas transformacijas iš eilės gautume: (1,2,3,4)->(1OR2=3,3OR4=7)->(3XOR7=4).

Kadangi duotai sekai a apskaičiuoti rezultatą v būtų per lengva, jums taip pat duota m užklausų. Kiekviena užklausą yra skaičių p,b pora. Užklausa p,b reiškia, jog elementui a_p turite priskirti reikšmę b ir po kiekvienos užklausos išvesti rezultatą v naujai sekai a.

Pradiniai duomenys

Pirmoje eilutėje pateikti du skaičiai n ir m (1\\leqn\\leq17,1\\leqm\\leq100000).

Antroje eilutėje pateikta 2^n sveikųjų skaičių a_1,a_2,...a_{2^n}(0\\leqa_i\\leq20^{30}).

Likusiose kiekvienoje m eilučių pateikti skaičiai p_i,b_i(1\\leqp_i\\leq2^n,0\\leqb_i\\leq2^{30}) - užklausos duomenys.

Rezultatai

Kiekvienai užklausai išvesti naujos sekos a rezultatą v.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
2 4
1 2 2 1 
3 1
2 2
2 2
3 3
 
2
2
2
0