Problem D
Stigavörður

Security guard eftir Collin Armstrong, Unsplash

Í hverri umferð getur leikmaður gert eina af eftirfarandi tveimur aðgerðum:

1. Velja einhvern reit og breyta tölunni sem er í þeim reit.

2. Velja tvær tölur $j$ og $k$, þannig að $1 \leq j \leq k \leq n$, og fá þá

   \[ a_ j \oplus a_{j + 1} \oplus \dots \oplus a_{k - 1} \oplus a_ k \]

   mörg stig, þar sem $a_ i$ er talan sem er á $i$-ta reitnum og $p\oplus q = \mathrm{gcd}(p,q)$ táknar stærsta sameiginlega deili $p$ og $q$, þ.e. stærstu heiltöluna $s$ þannig að bæði $p/s$ og $q/s$ hefur engan afgang.

Þú veist ekki alveg hvað markmið leiksins er, en það er algjört aukaatriði. Það eina sem þú þarft að gera er að halda utan um stigin.

Inntak

Fyrsta lína inniheldur tvær heiltölur $n$ og $q$ ($1 \leq n, q \leq 10^5$), fjöldi reita og fjöldi umferða. Önnur lína inniheldur $n$ heiltölur $a_1, a_2, \ldots , a_ n$ ($1 \leq a_ i \leq 10^9$), þar sem $a_ i$ er upprunalega talan á reit númer $i$. Næstu $q$ línur tákna umferðirnar, en hver þeirra inniheldur þrjár tölur $x$, $y$ og $z$. Ef $x=1$, þá breytti leikmaðurinn tölunni á reit númer $y$ í töluna $z$ ($1 \leq y \leq n$, $1 \leq z \leq 10^9$). En ef $x=2$ þá framkvæmdi leikmaðurinn seinni aðgerðina með $j=y$ og $k=z$ ($1\leq y \leq z \leq n$), og fær stig samkvæmt því.

Úttak

Fyrir hverja umferð þar sem leikmaður framkvæmdi seinni aðgerðina, skrifið út eina línu með stigunum sem leikmaðurinn fékk í þeirri umferð.

Stigagjöf

4 7
1000000000 7 4 100
2 1 1
2 2 2
2 3 3
2 4 4
2 1 4
1 2 6
2 1 4

1000000000
7
4
100
1
2