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;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
#define pb push_back
#define INF 1e15

class SegTree {
public:
	int n;
	VL nodes;
	VL lazy;
	SegTree(VL a) {
		int size = a.size();
		n = 1;
		while(n < size) n *= 2;
		nodes.resize(n * 2 - 1);
		lazy.resize(n * 2 - 1, 0);
		for (int i = 0; i < size; ++i) {
			nodes[i + n - 1] = a[i];
		}
		for (int i = size; i < n; ++i) {
			nodes[i + n - 1] = INF;
		}
		for (int i = n - 2; i >= 0; --i) {
			nodes[i] = min(nodes[i * 2 + 1], nodes[i * 2 + 2]);
		}
	}

	void eval(int k, int l, int r) {
		if(lazy[k] != 0) {
			nodes[k] += lazy[k];
			if(r - l > 1) {
				lazy[k * 2 + 1] += lazy[k];
				lazy[k * 2 + 2] += lazy[k];
			}
			lazy[k] = 0;
		}
	}

	void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
		if(r < 0) r = n;
		eval(k, l, r);
		if(r <= a || b <= l) return;
		if(a <= l && r <= b) {
			lazy[k] += x;
			eval(k, l, r);
		}else {
			add(a, b, x, k * 2 + 1, l, (l + r) / 2);
			add(a, b, x, k * 2 + 2, (l + r) / 2, r);
			nodes[k] = min(nodes[k * 2 + 1], nodes[k * 2 + 2]);
		}
	}

	ll get(int a, int b, int k = 0, int l = 0, int r = -1) {
		if(r < 0) r = n;
		eval(k, l, r);
		if(r <= a || b <= l) return INF;
		if(a <= l && r <= b) {
			return nodes[k];
		}else {
			ll ml = get(a, b, k * 2 + 1, l, (l + r) / 2);
			ll mr = get(a, b, k * 2 + 2, (l + r) / 2, r);
			return min(ml, mr);
		}
	}
};

int main(int argc, char **argv) {
	int n, q;
	cin >> n >> q;
	VL a(n, 0);
	SegTree st(a);
	VVL qu(q, VL(4));
	for (int i = 0; i < q; ++i) {
		cin >> qu[i][0];
		if(qu[i][0] == 0) {
			cin >> qu[i][1] >> qu[i][2] >> qu[i][3];
		}else {
			cin >> qu[i][1] >> qu[i][2];
		}

	}
	for (int i = 0; i < q; ++i) {
		if(qu[i][0] == 0) {
			st.add(qu[i][1], qu[i][2] + 1, qu[i][3]);
		}else {
			cout << st.get(qu[i][1], qu[i][2] + 1) << endl;
		}
//		for (int i = 0; i < st.nodes.size(); ++i) {
//			cout << st.nodes[i] << " ";
//		}
//		cout << endl;
	}
	return 0;
}