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>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

struct RMQ{
	using T = long long;
	T operator()(const T &a, const T &b) { return min(a,b); };
	static constexpr T identity() { return 0; }
};

template<class Monoid>
class rangeAddQuery{
	private:
		using T = typename Monoid::T;
		Monoid op;
		const int n;
		vector<T> dat, lazy;
		T query(int a, int b, int k, int l, int r){
			eval(k);
			if(b <= l || r <= a) return LLONG_MAX;
			else if(a <= l && r <= b) return dat[k];
			else{
				T left = query(a, b, k * 2, l, (l + r) / 2);
				T right = query(a, b, k * 2 + 1, (l + r) / 2, r);
				propTo(k);
				return op(left, right);
			}
		}
		void add(int a, int b, int k, int l, int r, T x){
			eval(k);
			if(a <= l && r <= b){
				lazy[k] += x;
				eval(k);
			}else if(l < b && a < r){
				add(a, b, k * 2, l, (l + r) / 2, x);
				add(a, b, k * 2 + 1, (l + r) / 2, r, x);
				propTo(k);
			}
		}
		inline void eval(int k){
			if(lazy[k] == op.identity()) return;
			dat[k] += lazy[k];
			if(k < n){
				lazy[k * 2] += lazy[k];
				lazy[k * 2 + 1] += lazy[k];
			}
			lazy[k] = op.identity();
		}
		inline void propTo(int k){
			dat[k] = op(dat[k * 2], dat[k * 2 + 1]);
		}
		int power(int n){
			int res = 1;
			while(n >= res) res*=2;
			return res;
		}
	public:
		rangeAddQuery(int n) : n(power(n)), dat(4 * n, op.identity()), lazy(4 * n, 0) {}
		rangeAddQuery(const vector<T> &v) : n(v.size()), dat(4 * n), lazy(4 * n, 0){
			copy(begin(v), end(v), begin(dat) + n);
			for(int i = n - 1; i > 0; i--) dat[i] = op(dat[2 * i], dat[2 * i + 1]);
		}
		T query(int a, int b){ return query(a,b,1,0,n); }
		void add(int s, int t, T x){ add(s, t, 1, 0, n, x); }
		T get(int a){ return query(a, a + 1); };
		void out(){
			rep(i,n * 2){ cout << dat[i + 1] << ' '; } cout << endl;
		}
};

int main(){
	int n, q;
	cin >> n >> q;

	rangeAddQuery<RMQ> seg(n);
	rep(i,q){
		int com;
		cin >> com;
		if(not com){
			int s, t, x;
			cin >> s >> t >> x;
			seg.add(s, t + 1, x);
		}else{
			int s, t;
			cin >> s >> t;
			cout << seg.query(s, t + 1) << endl;
		}
		//seg.out();
	}
}