# Stigavörður

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. They can change the number on a single tile. They can also choose two numbers $j$ and $k$, such that $1 \leq j \leq k \leq n$, and they score

\[ a_ j \oplus a_{j + 1} \oplus \dots \oplus a_{k - 1} \oplus a_ k \]points, where $a_ j$ is the $j$-th tile and $a \oplus b = \text {gcd}(a, b)$. You aren’t quite sure what the goal of the game is, but that doesn’t matter. All you need to do is keep track of the scores.

## Input

The first line of the input contains two integers, $1 \leq n \leq 10^5$ and $1 \leq q \leq 10^5$. The next line contains $n$ integers all larger than zero, but none larger than $10^9$. The next $q$ lines all 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 conatain a line with the score achieved that turn.

Sample Input 1 | Sample Output 1 |
---|---|

4 5 1000000000 2 4 100 2 1 1 2 2 2 2 3 3 2 4 4 2 1 4 |
1000000000 2 4 100 2 |