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;

/*
	UNITY_NODE minの単位元
	UNITY_LAZY addの単位元
	nodeの初期値に注意(constructor)
*/
template <class NODE, class LAZY, NODE UNITY_NODE, LAZY UNITY_LAZY>
struct LazySegTree {
// edit start
	void add(LAZY &a, LAZY b) {
		a += b;
	}
	void reflect(NODE& a, LAZY b, int l, int r) {
		a += b;
	}
	NODE merge(NODE a, NODE b) {
		return min(a, b);
	}
// end
	int n;
	vector<NODE> node;
	vector<LAZY> lazy;

	LazySegTree(int sz) : n(calc_n_size(1, sz)), node(2*n-1, 0), lazy(2*n-1, UNITY_LAZY) {}
	LazySegTree(const vector<NODE>& v) : n(calc_n_size(1, v.size())), node(2*n-1, UNITY_NODE), lazy(2*n-1, UNITY_LAZY) {
		for (int i = 0; i < v.size(); i++) node[n-1+i] = v[i];
		for (int i = n - 2; i >= 0; i--) renode(i);
	}

	int calc_n_size(int n_, int sz) {return n_ < sz ? calc_n_size(n_ * 2, sz) : n_;}
	void eval(int l, int r, int k) {
		reflect(node[k], lazy[k], l, r);
		if (r - l > 1) {
			add(lazy[k*2+1], lazy[k]);
			add(lazy[k*2+2], lazy[k]);
		}
		lazy[k] = UNITY_LAZY;
	}
	void renode(int k) {
		node[k] = merge(node[k*2+1], node[k*2+2]);
	}
	void set(int a, int b, LAZY x, int k, int l, int r) {
		if (b <= l || r <= a) {
			eval(l, r, k);
		} else if (a <= l && r <= b) {
			add(lazy[k], x);
			eval(l, r, k);
		} else {
			eval(l, r, k);
			set(a, b, x, k*2+1, l, (l+r) / 2);
			set(a, b, x, k*2+2, (l+r) / 2, r);
			renode(k);
		}
	}
	NODE get(int a, int b, int k, int l, int r) {
		eval(l, r, k);
		if (b <= l || r <= a) {
			return UNITY_NODE;
		} else if (a <= l && r <= b) {
			return node[k];
		} else {
			NODE t1 = get(a, b, 2*k+1, l, (l+r) / 2);
			NODE t2 = get(a, b, 2*k+2, (l+r) / 2, r);
			renode(k);
			return merge(t1, t2);
		}
	}
	NODE get(int a, int b) {return get(a, b, 0, 0, n);}
	void set(int a, int b, LAZY x) {set(a, b, x, 0, 0, n);}
};

int main() {
	int n, Q;
	cin >> n >> Q;
	LazySegTree<int, int, INT_MAX, 0> L(vector<int>(n, 0));
	while (Q--) {
		int q;
		cin >> q;
		if (q == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			L.set(s, t+1, x);
		} else {
			int s, t;
			cin >> s >> t;
			cout << L.get(s, t+1) << endl;
		}
	}
}