such molds lined up in a row. He knows that the batter inside the -th taiyaki still needs to cook for more seconds to be done. As running a specialty tea house is a lot of work, he wants you to help him answer queries, each of which is one of the following types:

is opening a specialty tea house! One of his famous dishes is taiyaki, which is typically cooked in small fish-shaped molds. has`1 x`

which means to print the amount of time the -th taiyaki still needs to be cooked.`2 x y t`

which means that considers cooking the pans for seconds. If it would cause one of the taiyaki to overcook (overcooking means that , where ), he ignores this instruction. Otherwise, he cooks each taiyaki in the range for seconds.`3 x y t`

which means that deems that the taiyaki in pans 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 for as the earlier pans get cooked a little when is pouring in the batter for the later pans. It is guaranteed that .`4 x y`

which means that reduces the cook times of each taiyaki in pans to the floor of the square root of its original cook time. That is for .

#### Constraints

In all subtasks,

##### Subtask 1 [10% of points]

##### Subtask 2 [20% of points]

There are no type `3`

or type `4`

operations.

##### Subtask 3 [20% of points]

There are no type `3`

operations.

##### Subtask 4 [50% of points]

No additional constraints.

#### Input Specification

The first line contains two integers, and .

The second line contains integers, , the initial cook times.

The next 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`

.

## Comments

Do you think you could add an extra sample input/output please :) ?