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 "stdio.h"
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

int mySize = 1;
vector<ll> val;
vector<ll> lazy;

void lazyPropagate(int p) {
    val[p] += lazy[p];
    if (p < mySize - 1) {
        lazy[(p * 2) + 1] += lazy[p];
        lazy[(p * 2) + 2] += lazy[p];
    }
    lazy[p] = 0;
}

void add(int l1, int r1, int l2, int r2, int k, int x) {
    if (r1 <= l2 || r2 <= l1) {
        lazyPropagate(k);
        return;
    }
    if (l1 <= l2 && r2 <= r1) {
        lazy[k] += x;
        lazyPropagate(k);
        return;
    }
    int mid = (l2 + r2) / 2;
    lazyPropagate(k);
    add(l1, r1, l2, mid, (k * 2) + 1, x);
    add(l1, r1, mid, r2, (k * 2) + 2, x);
    val[k] = min(val[(k * 2) + 1],val[(k * 2) + 2]);
}

void add(int l1, int r1, int x) {
    add(l1, r1, 0, mySize, 0, x);
}

ll getMin(int l1, int r1, int l2, int r2, int k) {
    if (r1 <= l2 || r2 <= l1) {
        return __LONG_LONG_MAX__;
    }
    if (l1 <= l2 && r2 <= r1) {
        lazyPropagate(k);
        return val[k];
    }
    int mid = (l2 + r2) / 2;
    lazyPropagate(k);
    ll sl = getMin(l1, r1, l2, mid, (k * 2) + 1);
    ll sr = getMin(l1, r1, mid, r2, (k * 2) + 2);
    return min(sl,sr);
}

ll getMin(int l1, int r1) {
    return getMin(l1, r1, 0, mySize, 0);
}

int main(){
    int n,q,command,l,r,value;
    scanf("%d %d",&n,&q);
    for(;mySize < n;mySize <<= 1);
    val = vector<ll>(mySize * 2,0);
    lazy = vector<ll>(mySize * 2,0);
    
    for(int i = 0;i < q;++i){
        scanf("%d" "%d" "%d",&command,&l,&r);
        // add(s,t,x): as,as+1,...,at にxを加算する。
        if(command == 0){
            scanf("%d",&value);
            add(l,r + 1,value);
            // find(s,t) : report the minimum value in as,as+1,...,at.
        }else{
            printf("%lld\n",getMin(l,r + 1));
        }
    }
}