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<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
#include<cstdlib>
#include<algorithm>

using namespace std;
#define pb push_back
#define mp make_pair
#define ls(x) (x << 1)
#define rs(x) (x<<1|1)
#define SZ(x) (int)(x).size()

typedef long long LL;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<LL, LL> pll;
typedef pair<bool, int> pbi;

const double eps = 1e-10;
const double PI = acos(-1.0);
//const double PI = 3.14159265358979323846264338327950288419716939937510
int dcmp(const double &x) { if (fabs(x) < eps) return 0; return x < 0 ? -1 : 1; }
const int MOD = 1e9 + 7;
const int INF = 2147483647;
const double INF_d = 1e64;

template<class T>
T qmod(T a, T b){ T ret = 1; while (b){ if (b & 1) ret *= a; b >>= 1; a *= a; } return ret; }
template<class T>
T gcd(T a, T b){ return !b ? a : gcd(b, a % b); }
template<class T>
T ex_gcd(T a, T b, T &x, T &y){
    if (!b){ x = 1, y = 0; return a; }
    T t, ret;
    ret = ex_gcd(b, a % b, x, y);
    t = x, x = y, y = t - a / b * y;
    return ret;
}
template<class T>
T inv(T t, T p){ return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p; }

// head

const int N = 2e5 + 7;
struct node{
    int l, r, tag, val;
};

int n, m, op, x, y, w;
node T[N << 2];

void build(int rt, int l, int r){
    T[rt].l = l, T[rt].r = r, T[rt].val = 0, T[rt].tag = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
}

void push_down(int rt){
    if (T[rt].tag){
        T[ls(rt)].tag += T[rt].tag, T[rs(rt)].tag += T[rt].tag;
        T[ls(rt)].val += T[rt].tag; T[rs(rt)].val += T[rt].tag;
        T[rt].tag = 0;
    }
}

void push_up(int rt){
    T[rt].val = min(T[ls(rt)].val, T[rs(rt)].val);
}

void update(int rt, int l, int r, int val){
    if (l > T[rt].r || r < T[rt].l) return;
    if (l <= T[rt].l && T[rt].r <= r){
        T[rt].val += val;
        T[rt].tag += val; return;
    }
    push_down(rt);
    int mid = (T[rt].l + T[rt].r) >> 1;
    if (l <= mid) update(ls(rt), l, r, val);
    if (r > mid) update(rs(rt), l, r, val);
    push_up(rt);
}

int query(int rt, int l, int r){
    if (l > T[rt].r || T[rt].l > r) return INF;
    if (l <= T[rt].l && T[rt].r <= r) return T[rt].val;
    push_down(rt);
    int ret = INF;
    int mid = (T[rt].l + T[rt].r) >> 1;
    if (l <= mid) ret = min(ret, query(ls(rt), l, r));
    if (r > mid) ret = min(ret, query(rs(rt), l, r));
    return ret;
}

int main(){
    //freopen("1.in", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for (int i = 0; i < m; i++){
        scanf("%d", &op);
        if (!op){
            scanf("%d%d%d", &x, &y, &w); x++, y++;
            update(1, x, y, w);
        }
        else{
            scanf("%d%d", &x, &y); x++, y++;
            printf("%d\n", query(1, x, y));
        }
    }
    return 0;
}