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:
#!/usr/bin/env python3
# DSL_2_H: RMQ and RAQ
# Range Minimum Query and Range Add Query
# Lazy propagate segment tree

from array import array
import sys


class SegmentTree:
    MAXV = 1000 * 10**5 + 1

    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = array('i', [0] * self.size)
        self.lazy = array('i', [0] * self.size)

    def add(self, lo, hi, v):
        def _add(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0

            if lo <= i and j <= hi:
                lz += v
                if lz:
                    data[r] += lz
                    if i < j:
                        lazy[left] += lz
                        lazy[right] += lz
            else:
                mid = (i + j) // 2
                if mid >= lo:
                    lv = _add(left, i, mid, lz)
                else:
                    lazy[left] += lz
                    lv = data[left] + lazy[left]

                if mid < hi:
                    rv = _add(right, mid+1, j, lz)
                else:
                    lazy[right] += lz
                    rv = data[right] + lazy[right]

                if lv < rv:
                    data[r] = lv
                else:
                    data[r] = rv

            return data[r]

        lazy = self.lazy
        data = self.data
        _add(0, 0, self.size//2, 0)

    def min(self, lo, hi):
        def _min(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0
            if lz:
                data[r] += lz

            if lo <= i and j <= hi:
                if lz and i < j:
                    lazy[left] += lz
                    lazy[right] += lz
                return data[r]
            else:
                mid = (i + j) // 2
                if mid >= lo:
                    lv = _min(left, i, mid, lz)
                else:
                    lazy[left] += lz
                    lv = self.MAXV

                if mid < hi:
                    rv = _min(right, mid+1, j, lz)
                else:
                    lazy[right] += lz
                    rv = self.MAXV

                if lv < rv:
                    return lv
                else:
                    return rv

        lazy = self.lazy
        data = self.data
        return _min(0, 0, self.size//2, 0)


def run():
    n, q = [int(i) for i in input().split()]

    tree = SegmentTree(n)

    ret = []
    for line in sys.stdin:
        com, *args = line.split()
        if com == '0':
            s, t, x = map(int, args)
            tree.add(s, t, x)
        elif com == '1':
            s, t = map(int, args)
            ret.append(tree.min(s, t))

    sys.stdout.write("\n".join([str(i) for i in ret]))
    sys.stdout.write("\n")


if __name__ == '__main__':
    run()