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 UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

class LazySegmentTree{
public:
	int n = 1;
	vector<int> node[3], lazy[2];
	void init(int N){
		while(n < N)n *= 2;
		rep(i,3)node[i].resize(2*n-1);
		rep(i,2)lazy[i].resize(2*n-1);
	}
	void lazy_evaluate(int k){
		rep(i,3)node[i][k] += lazy[i/2][k];
		if(k < n-1){
			rrep(i,2)lazy[0][2*k+i] += lazy[0][k];
			rrep(i,2)lazy[1][2*k+i] += lazy[1][k]/2;
		}
		rep(i,2)lazy[i][k] = 0;
	}
	void update(int a, int b, int x, int k, int l, int r){
		lazy_evaluate(k);
		if(r <= a || b <= l)return;
		if(a <= l && r <= b){
			lazy[0][k] += x;
			lazy[1][k] += (r-l)*x;
			lazy_evaluate(k);
			return;
		}
		update(a, b, x, k*2+1, l, (l+r)/2);
		update(a, b, x, k*2+2, (l+r)/2, r);
		node[0][k] = max(node[0][k*2+1], node[0][k*2+2]);
		node[1][k] = min(node[1][k*2+1], node[1][k*2+2]);
		node[2][k] = node[2][k*2+1]+node[2][k*2+2];
	}
	int calc(int a, int b, int k, int l, int r, int f){
		lazy_evaluate(k);
		if(r <= a || b <= l)return !f ? -INF : f==1 ? INF : 0;
		if(a <= l && r <= b)return node[f][k];
		int vl = calc(a, b, k*2+1, l, (l+r)/2, f);
		int vr = calc(a, b, k*2+2, (l+r)/2, r, f);
		return !f ? max(vl, vr) : f==1 ? min(vl, vr) : vl+vr;
	}
	void add(int a, int b, int x){update(a, b, x, 0, 0, n);}
	int get_max(int a, int b){return calc(a, b, 0, 0, n, 0);}
	int get_min(int a, int b){return calc(a, b, 0, 0, n, 1);}
	int get_sum(int a, int b){return calc(a, b, 0, 0, n, 2);}
};

signed main(){
	int n, q, MAX = (1LL<<31)-1;
	scanf("%lld%lld", &n, &q);
	LazySegmentTree seg;
	seg.init(n+1);
	//rep(i,n)seg.replace(i, i+1, MAX);
	
	rrep(i,q){
		int c, s, t, x;
		scanf("%lld",&c);
		if(c == 0){
			scanf("%lld%lld%lld", &s, &t, &x);
			seg.add(s, t+1, x);
		}else{
			scanf("%lld%lld", &s, &t);
			printf("%lld\n", seg.get_min(s, t+1));
		}
	}
	return 0;
}