Given an array $A$ of $n$ integers. Your task is to process $q$ queries of the form either form:
- `1 i x`, $A_i= x$
- `2 l r`, calculate:
$$\sum_{x=l}^{r} \sum_{y=x}^{r} A_x \oplus A_{x+1} \oplus ... \oplus A_y$$
where $\oplus$ is the XOR operator.
### Input
- The first line contains two integers $n,q$.
- The second line contains $n$ integer $A_i$.
- The next $q$ lines, each line contains a query of the above format.
### Output
- Print an integer which is the answer for each query of type $2$.
### Constraints
- $1 \le n, q \le 10^5$.
- $1 \le A_i,x \le 10^9$.
- $1 \le l \le r \le n$.
### Example
Input:
```
9 8
6 6 6 5 1 10 2 1 6
2 3 8
1 9 4
2 7 8
2 2 6
1 2 9
2 1 2
2 2 2
1 5 7
```
Output:
```
150
6
93
30
9
```
