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=\left\lfloor \sqrt{t_i} \right\rfloor~ for ~x \le i \le y~.

Constraints

In all subtasks,
~1 \le N \le 100\,000~
~1 \le Q \le 500\,000~
~1 \le x \le y \le N~
~1 \le t_i, t \le 10^{18}~

Subtask 1 [10%]

~1 \le N, Q \le 2\,000~

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.