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 CPP):

Solution:

#include <vector>
#include <climits>
#include <cstdio>
using namespace std;

class SegmentTree {
    const int N; // array size
    const int M; // initial value of the tree
    const int O; // initial value of the query
    const int H; // height of the tree, the highest significant bit in N

    int (*f)(int, int); // query operation
    int (*g)(int, int); // update operation

public:
    vector<int> t; // tree
    vector<int> d; // delayed tree

    SegmentTree(int N, int M, int O, int (*f)(int, int)) :
            N(N), M(M), O(O), H(sizeof(int) * 8 - __builtin_clz(N)), f(f), g(f), t(2 * N, M), d(N) {}

    SegmentTree(int N, int M, int O, int (*f)(int, int), int (*g)(int, int)) :
            N(N), M(M), O(O), H(sizeof(int) * 8 - __builtin_clz(N)), f(f), g(g), t(2 * N, M), d(N) {}

    void apply(int p, int val) {
        t[p] = g(val, t[p]);
        if (p < N) d[p] = g(val, d[p]);
    }

    void build(int p) {
        while (p > 1) {
            p >>= 1;
            t[p] = g(d[p], f(t[p << 1], t[p << 1 | 1]));
        }
    }

    void push(int p) {
        for (int s = H; s > 0; --s) {
            int i = p >> s;
            if (d[i] != 0) {
                apply(i << 1, d[i]);
                apply(i << 1 | 1, d[i]);
                d[i] = 0;
            }
        }
    }

    void update(int l, int r, int val) { // update val at interval [l, r)
        if (val == 0) return;
        l += N, r += N;
        int l0 = l, r0 = r;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, val);
            if (r & 1) apply(--r, val);
        }
        build(l0);
        build(r0 - 1);
    }

    int query(int l, int r) { // query on interval [l, r)
        l += N, r += N;
        push(l);
        push(r - 1);
        int res = O;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = f(t[l++], res);
            if (r & 1) res = f(t[--r], res);
        }
        return res;
    }
};

void test() {
    int n, q;
    scanf("%d%d", &n, &q);

    SegmentTree T(n, 0, INT_MAX,
                  [](int a, int b) { return min(a, b); },
                  [](int a, int b) { return a + b; }
    );

    while (q--) {
        int type;
        scanf("%d", &type);
        if (type) {
            int s, t;
            scanf("%d%d", &s, &t);
            printf("%d\n", T.query(s, t + 1));
        } else {
            int s, t, x;
            scanf("%d%d%d", &s, &t, &x);
            T.update(s, t + 1, x);
        }
    }
}

int main() {
    test();
}