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:
//RMQ and RAQ
//https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_H
#include <bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

ll *min_data,*max_data,*add_data;
int N = 1;

void init(ll first_N){
	while(N < first_N)N *= 2;
}

void add(int left,int right,ll value,int node_id,int node_left,int node_right){
	if(right < node_left || left > node_right) return;
	else if(left <= node_left && right >= node_right){
		add_data[node_id] += value;
		while(node_id != 0){
			node_id = (node_id-1)/2;
			min_data[node_id] = min(min_data[2*node_id+1]+add_data[2*node_id+1],min_data[2*node_id+2]+add_data[2*node_id+2]);
			max_data[node_id] = max(max_data[2*node_id+1]+add_data[2*node_id+1],max_data[2*node_id+2]+add_data[2*node_id+2]);
		}
	}else{
		add(left,right,value,2*node_id+1,node_left,(node_left+node_right)/2);
		add(left,right,value,2*node_id+2,(node_left+node_right)/2+1,node_right);
	}
}
//getMin(s,t)で[s,t]に対する最小
ll getMin(int left,int right,int node_id,int node_left,int node_right){
	if(right < node_left || left > node_right)return BIG_NUM;
	else if(left <= node_left && right >= node_right) return min_data[node_id]+add_data[node_id];
	else{
		ll  left_min  = getMin(left,right,2*node_id+1,node_left,(node_left+node_right)/2);
		ll  right_min = getMin(left,right,2*node_id+2,(node_left+node_right)/2+1,node_right);
		return min(left_min,right_min)+add_data[node_id];
	}
}

//getMin(s,t)で[s,t]に対する最大
ll getMax(int left,int right,int node_id,int node_left,int node_right){
	if(right < node_left || left > node_right)return -BIG_NUM;
	else if(left <= node_left && right >= node_right) return max_data[node_id]+add_data[node_id];
	else{
		ll  left_max  = getMax(left,right,2*node_id+1,node_left,(node_left+node_right)/2);
		ll  right_max = getMax(left,right,2*node_id+2,(node_left+node_right)/2+1,node_right);
		return max(left_max,right_max)+add_data[node_id];
	}
}

//問題は0-indexedで与えられている
int main(){
	int n,q; cin >> n >> q;
	init(n);

	min_data = new ll[2*N-1];
	max_data = new ll[2*N-1];
	add_data = new ll[2*N-1];

	for(ll i = 0; i <= 2*N-2; i++){
		min_data[i] = 0;
		max_data[i] = 0;
		add_data[i] = 0;
	}

	int command,left,right;
	ll value;
	for(int loop = 0; loop < q; loop++){
		cin >> command;
		if(command == 0){
			cin >> left >> right >> value;
			add(left,right,value,0,0,N-1);
		}else{
			cin >> left >> right;
			cout << getMin(left,right,0,0,N-1) << endl;
		}
	}
	return 0;
}