Problem: Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

* $add(s, t, x)$ : add $x$ to $a_s, a_{s+1}, ..., a_t$.
* $find(s, t)$ : report the minimum value in $a_s, a_{s+1}, ..., a_t$.



Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ are 0.

Constraints

* $1 ≤ n ≤ 100000$
* $1 ≤ q ≤ 100000$
* $0 ≤ s ≤ t < n$
* $-1000 ≤ x ≤ 1000$

Input


$n$ $q$
$query_1$
$query_2$
:
$query_q$


In the first line, $n$ (the number of elements in $A$) and $q$ (the number of queries) are given. Then, $i$th query $query_i$ is given in the following format:


0 $s$ $t$ $x$


or


1 $s$ $t$


The first digit represents the type of the query. '0' denotes $add(s, t, x)$ and '1' denotes $find(s, t)$.

Output

For each $find$ query, print the minimum value.

Example

Input

6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5


Output

-2
0
1
-1

Solution (in PYTHON3):

Solution:
import sys
input = sys.stdin.readline
INF = 2**31 - 1

class StarrySkyTree:
    def __init__(self, n):
        LV = (n-1).bit_length()
        self.N0 = 2 ** LV
        self.data = [0] * (2*self.N0)
        self.lazy = [0] * (2*self.N0)
    
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        
        while L < R:
            if R <= rm:
                yield R
                
            if L <= lm:
                yield L
                
            L >>= 1; R >>= 1
            
        while L:
            yield L
            L >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            
            if not v:
                continue
            
            self.lazy[2*i-1] += v; self.lazy[2*i] += v
            self.data[2*i-1] += v; self.data[2*i] += v
            self.lazy[i-1] = 0

    def update(self, l, r, x):
        L = self.N0 + l; R = self.N0 + r
        
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x; self.data[R-1] += x
                
            if L & 1:
                self.lazy[L-1] += x; self.data[L-1] += x
                L += 1
                
            L >>= 1; R >>= 1
            
        for i in self.gindex(l, r):
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = INF
        
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
                
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
                
            L >>= 1; R >>= 1
            
        return s

n, q = map(int, input().split())
sst = StarrySkyTree(n)

for _ in range(q):
    que = list(map(int, input().split()))
    
    if que[0] == 0:
        s, t, x = que[1], que[2], que[3]
        sst.update(s, t+1, x)
    elif que[0] == 1:
        s, t = que[1], que[2]
        print(sst.query(s, t+1))