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:
from array import array


class SegmentTree(object):
    MAXV = 1000 * 10**5 + 1

    def __init__(self, n: int) -> None:
        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, l: int, h: int, v: int) -> None:
        def _add(r, i: int, j: int, lz: int) -> int:
            left, right = r * 2 + 1, r * 2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0

            if (l <= i and j <= h):  # noqa: E741
                lz += v
                if lz:
                    data[r] += lz
                    if (i < j):
                        lazy[left] += lz
                        lazy[right] += lz
            else:
                mid = (i + j) // 2
                if (mid >= l):
                    lv = _add(left, i, mid, lz)
                else:
                    lazy[left] += lz
                    lv = data[left] + lazy[left]

                if (mid < h):
                    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, l: int, h: int) -> int:
        def _min(r, i: int, j: int, lz: int) -> int:
            left, right = r * 2 + 1, r * 2 + 2
            if lazy[r]:
                lz += lazy[r]
                lazy[r] = 0
            if lz:
                data[r] += lz

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

                if (mid < h):
                    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)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    segtree = SegmentTree(n)

    ans = []
    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            segtree.add(v[0], v[1], v[2])
        else:
            ans.append(segtree.min(v[0], v[1]))

    print("\n".join(map(str, ans)))