Problem F
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\le j\le k\le n$, og fá þá

   $$a_j\oplus a_{j+1}\oplus \cdots \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=\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\le n,q\le {10}^5$), fjöldi reita og fjöldi umferða. Önnur lína inniheldur $n$ heiltölur $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {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\le y\le n$, $1\le z\le {10}^9$). En ef $x=2$ þá framkvæmdi leikmaðurinn seinni aðgerðina með $j=y$ og $k=z$ ($1\le y\le z\le 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