Alice purchased an array of wooden boxes that she indexed from to . On each box , she writes an integer that we'll refer to as .

Alice wants you to perform *operations* on the array of boxes. Each operation is in one of the following forms:

(Note: For each type of operations, )

`1 l r c`

: Add to each . Note that can be negative.`2 l r d`

: Replace each with .`3 l r`

: Print the minimum value of any .`4 l r`

: Print the sum of all .

Recall that is the maximum integer such that (e.g., and ).

Given , the value of each , and operations, can you perform all the operations efficiently?

**Input Format**

The first line contains two space-separated integers denoting the respective values of (the number of boxes) and (the number of operations).

The second line contains space-separated integers describing the respective values of (i.e., the integers written on each box).

Each of the subsequent lines describes an *operation* in one of the four formats defined above.

**Constraints**

**Output Format**

For each operation of type or type , print the answer on a new line.

**Sample Input 0**

```
10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
```

**Sample Output 0**

```
-2
-2
-2
-2
0
1
1
```

**Explanation 0**

Initially, the array of boxes looks like this:

We perform the following sequence of operations on the array of boxes:

The first operation is

`1 0 4 1`

, so we add to each where :

The second operation is

`1 5 9 1`

, so we add to each where :

- The third operation is
`2 0 9 3`

, so we divide each where by and take the floor:

- The fourth operation is
`3 0 9`

, so we print the minimum value of for , which is the result of . - The fifth operation is
`4 0 9`

, so we print the sum of for , which is the result of .

... and so on.