little_prince is opening a specialty tea house! One of his famous dishes is taiyaki, which is typically cooked in small fish-shaped molds. little_prince has $N$ such molds lined up in a row. He knows that the batter inside the $i$-th taiyaki still needs to cook for $t_i$ more seconds to be done. As running a specialty tea house is a lot of work, he wants you to help him answer $Q$ queries, each of which is one of the following types:

• 1 x which means to print the amount of time the $i$-th taiyaki still needs to be cooked.

• 2 x y t which means that little_prince considers cooking the pans $x,x+1,\dots ,y$ for $t$ seconds. If it would cause one of the taiyaki to overcook (overcooking means that $t>t_i$, where $x\le i\le y$), he ignores this instruction. Otherwise, he cooks each taiyaki in the range for $t$ seconds.

• 3 x y t which means that little_prince deems that the taiyaki in pans $x,x+1,\dots ,y$ are not up to standard. He pours new batter into the pans starting from left to right at a rate of one pan per second while the pans are heating. This means that the cook times of the pans becomes $t_i=t-y+i$ for $x\le i\le y$ as the earlier pans get cooked a little when little_prince is pouring in the batter for the later pans. It is guaranteed that $t-y+x\ge 0$.

• 4 x y which means that little_prince reduces the cook times of each taiyaki in pans $x,x+1,\dots ,y$ to the floor of the square root of its original cook time. That is $t_i=\lfloor \sqrt{t_i}\rfloor$ for $x\le i\le y$.

Constraints

In all subtasks,
$1\le N\le 100000$
$1\le Q\le 500000$
$1\le x\le y\le N$
$1\le t_i,t\le {10}^{18}$

Subtask 1 [10%]

$1\le N,Q\le 2000$

Subtask 2 [20%]

There are no type 3 or type 4 operations.

Subtask 3 [20%]

There are no type 3 operations.

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains two integers, $N$ and $Q$.
The second line contains $N$ integers, $t_1,t_2,\dots ,t_N$, the initial cook times.
The next $Q$ lines each contain a query, in the format as described above.

Output Specification

Output one integer on a separate line for each type 1 query.

Sample Input

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

Sample Output

1
3
0

Explanation for Sample Output

The first operation cannot be completed as it would cause the third taiyaki to overcook. Therefore, the array is 1 3 1 7 6.
After the second operation, the array is 1 1 1 7 6.
After the fourth operation, the array is 1 2 3 4 6.
After the sixth operation, the array is 1 1 1 2 2.
After the seventh operation, the array is 0 0 0 1 2.