Problem D
Stigavörður

Security guard by Collin Armstrong, Unsplash

You really like playing games with your friend. This time, however, you are stuck being the score keeper for two of your friends. They are playing a game where $n$ numbered tiles lay on the board in a line. The players can do one of two moves each turn:

1. Select a single tile and change the number on a that tile.

2. Select some two numbers $j$ and $k$, such that $1 \leq j \leq k \leq n$ and score

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

   points, where $a_ i$ is the number on the $i$-th tile and $p\oplus q = \mathrm{gcd}(p,q)$ represents the greatest common divisor of $p$ and $q$, that is, the largest integer $s$ such that both $p/s$ and $q/s$ have no remainder.

You are not quite sure what the goal of the game is, but that does not matter. All you need to do is keep track of the scores.

Input

The first line of the input contains two integers $n$ and $q$, where $1 \leq n \leq 10^5$ and $1 \leq q \leq 10^5$. The next line contains $n$ integers, all of which are larger than zero, but none of which are larger than $10^9$. The next $q$ lines each contain three integers $x$, $y$, and $z$. Each line describes a single turn in the game. The integer $x$ is either $1$ or $2$. If $x=1$, then $1 \leq y \leq n$ and $1 \leq z \leq 10^9$, and this means a player changed the number on the $y$-th tile to $z$. If $x=2$, then $1 \leq y \leq z \leq n$, and this means a player scored, as described above, with $j=y$ and $k=z$.

Output

For each turn in the game, in order, where a player scores, the output should contain a line with the score achieved that turn.

Scoring

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