Tudor likes ice cream cones!

One day, Tudor travels to an ice cream convention to eat ice cream. There are $N$ stands, numbered $1$ through $N$. Stand $k$ is serving flavor $\lceil \frac{k}{\sqrt{N}}\rceil$.

Each of the stands charges a certain price for ice cream, which Tudor interprets as a signal of the quality of the ice cream. Tudor has strong flavor preferences and will decide to order ice cream from two stands within certain flavor constraints, choosing to either order from the two stands with the highest price, in the event he wishes to try some gourmet ice cream, or the two stands with the lowest price, in the event he wishes to save on money.

As the convention goes on, stands may change their prices. Tudor's flavor preferences may also change. Help Tudor eat ice cream!

Input Specification

The first line contains two positive integers, $N$ and $Q$. You may assume $N$ and $Q$ are no larger than ${10}^6$. Furthermore, $N$ will be a perfect square and will not be equal to 1.

The next line contains $N$ positive integers, the costs of each of the $N$ stands in order. No stand will exceed ${10}^9$ in cost.

Each of the next $Q$ lines contains three integers. The first integer in each line will be either $1$, $2$, or $3$. The remaining integers on the line will be encoded. All encoded integers should be decoded by XOR'ing them with the answer of the most recent query. In the event there were no prior answers, XOR the encoded integers with $0$.

If the first integer in the line is 1, the next two integers are $i^{\prime }$ and $v^{\prime }$, indicating that stand $i$ should have value $v$. The decoded value $i$ will satisfy $1\le i\le N$. The decoded value $v$ will satisfy $1\le v\le {10}^9$.

If the first integer in the line is 2, the next two integers are $l^{\prime }$ and $r^{\prime }$, indicating that Tudor wishes to know the sum of the prices of the two cheapest stands that offer a flavor between $l$ and $r$. The decoded values $l$ and $r$ will satisfy $1\le l\le r\le \sqrt{N}$.

If the first integer in the line is 3, the next two integers are $l^{\prime }$ and $r^{\prime }$, indicating that Tudor wishes to know the sum of the prices of the two most expensive stands that offer a flavor between $l$ and $r$. The decoded values $l$ and $r$ will satisfy $1\le l\le r\le \sqrt{N}$.

Output Specification

For each query, output the desired cost on a separate line.

Sample Data ZIP

Click here for ZIP.

Sample Input

4 4
1 4 2 5
2 1 1
2 7 7
1 3 6
3 6 5

Sample Output

5
7
6