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