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 <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i < ((int)(b)); ++i)
#define rrep(i, a, b) for (int i = ((int)(b)) - 1; i >= (a); --i)
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
using pii = pair<int, int>;
using vvi = vector<vector<int>>;
using vi = vector<int>;
constexpr int INF = 1001001001001001001LL;

void dump_impl(string s) {}
template <class H, class... T>
void dump_impl(string s, const H &head, const T&... tail) {
    int par = 0;
    rep(i, 0, sz(s)) {
        char ch = s[i];
        if (ch == ',' && par == 0) {
            cerr << " = " << head << ", ";
            dump_impl(s.substr(i + 1), tail...);
            return;
        } else {
            cerr << ch;
            if (ch == '(') par++;
            if (ch == ')') par--;
        }
    }
}
#define dump(...) do { cerr << "\x1b[33;1m"; dump_impl(#__VA_ARGS__ ",", __VA_ARGS__); cerr << "\x1b[0m" << endl; } while (0)

template <class T>
struct LazySegmentTree {
    const T query_ident = INF;
    const T prop_ident = 0;
    int size;
    vector<T> data;
    vector<T> lazy;
    vi width;

    LazySegmentTree(int n) {
        size = 1;
        while (size < n) size *= 2;
        data.assign(size * 2, query_ident);
        lazy.assign(size * 2, prop_ident);
        width.assign(size * 2, 1);
        rrep(k, 0, size - 1) {
            width[k] = width[k * 2 + 1] + width[k * 2 + 2];
        }
    }
    void lazy_propagate(int k) {
        if (lazy[k] == prop_ident) return;
        data[k] += lazy[k];  // !
        if (k < size - 1) {
            lazy[k * 2 + 1] += lazy[k];  // !
            lazy[k * 2 + 2] += lazy[k];  // !
        }
        lazy[k] = prop_ident;
    }
    void range_add(int ql, int qr, T value) {
        range_add(ql, qr, value, 0, 0, size);
    }
    void range_add(int ql, int qr, T value, int k, int nl, int nr) {
        if (qr <= nl || nr <= ql) {
            lazy_propagate(k);
            return;
        }
        if (ql <= nl && nr <= qr) {
            lazy[k] += value;  // !
            lazy_propagate(k);
            return;
        }
        lazy_propagate(k);
        int nm = (nl + nr) / 2;
        range_add(ql, qr, value, k * 2 + 1, nl, nm);
        range_add(ql, qr, value, k * 2 + 2, nm, nr);
        data[k] = min(data[k * 2 + 1], data[k * 2 + 2]);  // !
    }
    T range_min(int ql, int qr) {
        return range_min(ql, qr, 0, 0, size);
    }
    T range_min(int ql, int qr, int k, int nl, int nr) {
        if (qr <= nl || nr <= ql) {
            return query_ident;
        }
        if (ql <= nl && nr <= qr) {
            lazy_propagate(k);
            return data[k];
        }
        lazy_propagate(k);
        int nm = (nl + nr) / 2;
        T res_l = range_min(ql, qr, k * 2 + 1, nl, nm);
        T res_r = range_min(ql, qr, k * 2 + 2, nm, nr);
        return min(res_l, res_r);  // !
    }
};

signed main() {
    int N, Q;
    cin >> N >> Q;
    LazySegmentTree<int> seg(N);
    seg.range_add(0, N, -INF);
    rep(i, 0, Q) {
        int com;
        cin >> com;
        if (com == 0) {
            int L, R, X;
            cin >> L >> R >> X;
            seg.range_add(L, R + 1, X);
        } else {
            int L, R;
            cin >> L >> R;
            cout << seg.range_min(L, R + 1) << endl;
        }
    }
}