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 mod 1000000007
#define dom 998244353
#define all(c) begin(c),end(c)
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
#define long long long
#define List vector
#define var auto
#define Count size()
#define Length size()
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

template <typename T, typename U>
struct LazySegTree {
	int n;
	function<T(T, T)> calc;
	function<T(T, U, int)> apply;
	function<U(U, U)> merge;
	T ex;
	vector<T> data;
	vector<U> lazy;
	vector<bool> is_lazy;
	LazySegTree(int n_, function<T(T, T)> calc,
		function<T(T, U, int)> apply,
		function<U(U, U)> merge,
		T ex){
		this->calc = calc;
		this->apply = apply;
		this->merge = merge;
		this->ex = ex;	
		init(n_);
	}
	void init(int n_) {
		n = 1;
		while (n < n_) n *= 2;
		data.clear();
		data.resize(2 * n - 1, ex);
		lazy.clear();
		lazy.resize(2 * n - 1, U());
		is_lazy.clear();
		is_lazy.resize(2 * n - 1, false);
	}
	void assign_lazy(int k, U x)
	{
		if (k >= (int)lazy.size()) return;
		if (is_lazy[k]) lazy[k] = merge(lazy[k], x);
		else
		{
			is_lazy[k] = true;
			lazy[k] = x;
		}
	}
	void eval(int len, int k) {
		if (!is_lazy[k]) return;
		assign_lazy(k * 2 + 1, lazy[k]);
		assign_lazy(k * 2 + 2, lazy[k]);
		data[k] = apply(data[k], lazy[k], len);
		is_lazy[k] = false;
	}
	T update(int a, int b, U x, int k, int l, int r) {
		eval(r - l, k);
		if (r <= a || b <= l) return data[k];
		if (a <= l && r <= b) {
			assign_lazy(k, x);
			return apply(data[k], lazy[k], r - l);
		}
		return data[k] = calc(update(a, b, x, k * 2 + 1, l, (l + r) / 2),
			update(a, b, x, k * 2 + 2, (l + r) / 2, r));
	}
	// [a, b]に対する閉区間更新 0-indexed
	T update(int a, int b, U x) {
		b++;
		return update(a, b, x, 0, 0, n);
	}
	T query(int a, int b, int k, int l, int r) {
		eval(r - l, k);
		if (r <= a || b <= l) return ex;
		if (a <= l && r <= b) return data[k];
		T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return calc(vl, vr);
	}
	// return node [a,b] 閉区間クエリ 0-indexed
	T query(int a, int b) {
		b++;
		return query(a, b, 0, 0, n);
	}

	//デバッグ用
	vector<T> items()
	{
		vector<T> ret(n);
		for (int i = 0; i < n; i++)
		{
			ret[i] = query(i, i);
		}
		return ret;
	}
};
//呼び出し方
//区間Add区間Sum
//LazySegTree<long, long> raq_rsq(N,
//	[](long a, long b) { return a + b; },
//	[](long a, long b, int len) { return a + b * len; },
//	[](long a, long b) { return a + b; },
//	0);
//区間Add区間Min

//区間変更区間Min
//LazySegTree<int, int> ruq_rmq(N,
//	[](int a, int b) { return min(a, b); },
//	[](int a, int b, int len) {return b; },
//	[](int a, int b) {return b; },
//	INT_MAX);

void solve()
{
	int N, Q;
	cin >> N >> Q;

	LazySegTree<long, long> raq_rmq(N,
	[](long a, long b) { return min(a, b); },
	[](long a, long b, int len) { return a + b; },
	[](long a, long b) { return a + b; },
	INT_MAX);

	raq_rmq.update(0, N - 1, -INT_MAX);
	rep(i, Q)
	{
		int com;
		cin >> com;
		if (com == 0)
		{
			int s, t, x;
			cin >> s >> t >> x;
			raq_rmq.update(s, t, x);
		}
		else
		{
			int s, t;
			cin >> s >> t;
			cout << raq_rmq.query(s, t) << endl;
		}
	}
	//auto p = raq_rmq.items();
	//rep(i, p.size())
	//{
	//	cout << p[i] << " ";
	//}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}