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:
//「場所iにいるとき、場所0～iのいずれかから買うことができる（ただし売り切れていなければ）」としても答えは変わらない.
//場所iでの行動は、「売り切れてない最安値を買う」→「移動する」が最適っぽい。
//B_i = (場所iで買える ? A_i : ∞）とし、B_iをRMQで管理すれば、最安値はO(logN)で求まる。B_iの更新をするために在庫管理をしたい。
//在庫管理は「StarrySky木」を用いるとO(logN)。（場所iでx_i本買うとして、y_i = x_0+…+x_iとおき、{y_i}を管理する。）
//よって、この問題はO(NlogN)で解けた。考察は簡単だけどStarrySky木の実装が初めてなので厳しい。
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define rep(i, n) for(i = 0; i < (n); i++)
#define int long long
using namespace std;
typedef pair<int, int> P;

namespace std {
	P operator+(const P &l, const P &r) {
		return P(l.first + r.first, l.second + r.second);
	}
}

//区間加算, 区間最小
const int DEPTH = 17;
const int INF = 1e+15;
struct StarrySky {
	int valAdd[1 << (DEPTH + 1)];	//valAdd[i] = ノードiに一様加算された値
	P   valMin[1 << (DEPTH + 1)];	//valMin[i] = (ノードiより上のvalAddを無視したときの、ノードiと対応する区間の最小値, 最小値の場所）
	
	StarrySky() {
		int i;
		rep(i, 1 << (DEPTH + 1)) { valAdd[i] = 0; valMin[i] = P(0, i - (1 << DEPTH) + 1); }
	}
	
	P add(int l, int r, int val, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) { return valMin[id]; }
		if (l <= a && b <= r) {
			valAdd[id] += val;
			valMin[id].first += val;
			return valMin[id];
		}
		
		P u = add(l, r, val, a, a + (b - a) / 2, id * 2 + 1);
		P v = add(l, r, val, a + (b - a) / 2, b, id * 2 + 2);
		return valMin[id] = min(u, v) + P(valAdd[id], 0);
	}
	
	void update(int pos, int x) {
		int leaf = pos + (1 << DEPTH) - 1;
		add(pos, pos + 1, x - valMin[leaf].first);
	}
	
	P getMin(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) { return P(INF, -1); }
		if (l <= a && b <= r) { return valMin[id]; }
		P u = getMin(l, r, a, a + (b - a) / 2, id * 2 + 1);
		P v = getMin(l, r, a + (b - a) / 2, b, id * 2 + 2);
		return min(u, v) + P(valAdd[id], 0);
	}
};

//問題
int n, q;
int t, l, r, x;
StarrySky sky;

signed main() {
	int i;
	
	cin >> n >> q;
	rep(i, q) {
		cin >> t >> l >> r; r++;
		if (t == 0) {
			cin >> x;
			sky.add(l, r, x);
		}
		else {
			cout << sky.getMin(l, r).first << endl;
		}
	}
	return 0;
}