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;

class RAQ {
public:
	struct Node {
		long long min; long long buf;
		Node(long long s, long long b) : min(s), buf(b) {}
	};
private:
	vector<Node> node;
	long long defval;
	long long nega;
	int N;
	int n;
public:
	void init(int n, long long defval = 0) {
		N = 1;
		while (N < n)N <<= 1;
		this->n = n;
		this->defval = defval;
		node.assign(N * 2 - 1, Node(defval, 0));
		nega = INT64_MAX;
	}
	long long query(int a, int b, int l = 0, int r = -1, int i = 0) {
		if (r == -1) r = N;
		if (b <= l || r <= a) return nega;
		if (a <= l && r <= b) return node[i].min;
		//int rag = min(r, b) - max(l, a);
		return min(query(a, b, l, (l + r) / 2, i * 2 + 1), query(a, b, (l + r) / 2, r, i * 2 + 2)) + node[i].buf;
	}
	void update(int a, int b, long long v, int l = 0, int r = -1, int i = 0) {
		if (r == -1) r = N;
		if (b <= l || r <= a) return;
		if (a <= l && r <= b) { node[i].buf += v; node[i].min += v; return; }

		update(a, b, v, l, (l + r) / 2, i * 2 + 1);
		update(a, b, v, (l + r) / 2, r, i * 2 + 2);

		node[i].min = min(node[i * 2 + 1].min, node[i * 2 + 2].min) + node[i].buf;
	}

};

int main() {
	int n, q; cin >> n >> q;
	RAQ tr; tr.init(n);

	vector<long long> ans;

	for (int i = 0; i < q; i++) {

		int c; cin >> c;
		if (c == 0) {
			int s, t, x; cin >> s >> t >> x;
			tr.update(s, t + 1, x);
		}
		else {
			int s, t; cin >> s >> t;
			ans.push_back(tr.query(s, t + 1));
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}

	return 0;
}