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 endl '\n'
#define MOD 1000000007
#define maxn 100010

int t[5 * maxn], lazy[5 * maxn];

int doit(int a, int b) {
    return min(a, b);
}

void build(int start, int end, int index = 1) {
    if (start == end) {
        t[index] = 0;
        return;
    }

    int mid = start + end >> 1;
    build(start, mid, index << 1);
    build(mid + 1, end, index << 1 | 1);

    t[index] = doit(t[index << 1], t[index << 1 | 1]);
}

void propagate(int start, int end, int index) {
    t[index] += lazy[index];
    if (start != end) {
        lazy[index << 1] += lazy[index];
        lazy[index << 1 | 1] += lazy[index];
    }
    lazy[index] = 0;
}

int query(int start, int end, int l, int r, int index = 1) {
    if (lazy[index] != 0)
        propagate(start, end, index);
    //Invalid range
    if (r < start or l > end)
        return INT_MAX;

    //In range
    if (l <= start and end <= r) {
        return t[index];
    }

    int mid = start + end >> 1;
    return doit(query(start, mid, l, r, index << 1), query(mid + 1, end, l, r, index << 1 | 1));
}

void pUpdate(int start, int end, int point, int val, int index = 1) {
    if (start == end) {
        t[index] += val;
        return;
    }

    int mid = start + end >> 1;
    if (point <= mid)
        pUpdate(start, mid, point, val, index << 1);
    else
        pUpdate(mid + 1, end, point, val, index << 1 | 1);

    t[index] = doit(t[index << 1], t[index << 1 | 1]);
}


void rangeUpdate(int start, int end, int l, int r, int val, int index) {
    if (lazy[index])
        propagate(start, end, index);
    
    if (l > end or r < start)
        return;

    if (l <= start and end <= r) {
        lazy[index] = val;
        propagate(start, end, index);
        return;
    }

    int mid = start + end >> 1;
    rangeUpdate(start, mid, l, r, val, index << 1);
    rangeUpdate(mid + 1, end, l, r, val, index << 1 | 1);

    t[index] = doit(t[index << 1], t[index << 1 | 1]);
}

void solve() {
    int n, q;
    cin >> n >> q;

    build(0, n - 1, 1);

    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;

        if (a == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            rangeUpdate(0, n - 1, s, t, x, 1);
        } else {
            int s, t;
            cin >> s >> t;

            cout << query(0, n - 1, s, t, 1) << endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}