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:
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
#define int long long
int seg_tree[seg_size*4];
int seg_sub[seg_size*4];
int seg_set(int now){
    seg_tree[now*2] += seg_sub[now*2];
    seg_sub[now*2*2] += seg_sub[now*2];
    seg_sub[now*2*2+1] += seg_sub[now*2];
    seg_sub[now*2] = 0;
    seg_tree[now*2+1] += seg_sub[now*2+1];
    seg_sub[(now*2+1)*2] += seg_sub[now*2+1];
    seg_sub[(now*2+1)*2+1] += seg_sub[now*2+1];
    seg_sub[now*2+1] = 0;
    seg_tree[now] = min(seg_tree[now*2],seg_tree[now*2+1]);
    if(now != 0) seg_set(now/2);
    return 0;
}
int seg_find(int now,int n_l,int n_r,int w_l,int w_r){
    seg_tree[now] += seg_sub[now];
    seg_sub[now*2] += seg_sub[now];
    seg_sub[now*2+1] += seg_sub[now];
    seg_sub[now] = 0;
    if(w_l <= n_l&&n_r <= w_r) return seg_tree[now];
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_find(now*2,n_l,(n_l+n_r)/2,w_l,w_r),seg_find(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r));
}
int seg_add(int now,int n_l,int n_r,int w_l,int w_r,int setting){
    seg_tree[now] += seg_sub[now];
    seg_sub[now*2] += seg_sub[now];
    seg_sub[now*2+1] += seg_sub[now];
    seg_sub[now] = 0;
    if(w_l <= n_l&&n_r <= w_r){
        seg_sub[now] += setting;
        seg_set(now/2);
        return seg_tree[now];
    }
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_add(now*2,n_l,(n_l+n_r)/2,w_l,w_r,setting),seg_add(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r,setting));
}
#undef int
int main(){
#define int long long
    int n,m;
    cin >> n >> m;
    REP(i,m){
        int a;
        cin >> a;
        if(a == 0){
            int b,c,d;
            cin >> b >> c >> d;
            seg_add(1,0,seg_size,b,c+1,d);
        }else{
            int b,c;
            cin >> b >> c;
            cout << seg_find(1,0,seg_size,b,c+1) << endl;
        }
    }
}