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 JAVA):

Solution:


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int q = Integer.parseInt(tmpArray[1]);

		SqrtDecompositionRMQRAQ sq = new SqrtDecompositionRMQRAQ(n);

		for(int i = 0; i < q ; i++){
			tmpArray = br.readLine().split(" ");
			if(tmpArray[0].equals("0")){
				sq.add(Integer.parseInt(tmpArray[1]), Integer.parseInt(tmpArray[2]) + 1, Integer.parseInt(tmpArray[3]));
			}

			else {
				System.out.println(sq.findMin(Integer.parseInt(tmpArray[1]), Integer.parseInt(tmpArray[2]) + 1));
			}
		}
	}

}

class SqrtDecompositionRMQRAQ {
	int N, K;
	long[] data;
	long[] bucketAdd;
	long[] bucketMin;
	static final int sqrtN = 512;

	public SqrtDecompositionRMQRAQ(int n) {
		N = n;
		K = (N + sqrtN - 1) / sqrtN;
		data = new long[K * sqrtN];
		bucketAdd = new long[K];
		bucketMin = new long[K];
	}

	void add(int s, int t, int x) {
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {
				bucketAdd[k] += x;
				bucketMin[k] += x;
			} else {
//				System.out.println("direct edit");
				for(int i = Math.max(s, l); i < Math.min(t, r); ++i) {
					data[i] += x;
				}
				bucketMin[k] = Integer.MAX_VALUE;
				for(int i = l; i < r; i++){
					bucketMin[k] = Math.min(bucketMin[k], data[i] + bucketAdd[k]);
				}
//				System.out.println("min "+ bucketMin[k]);
			}
		}
	}

	long findMin(int s, int t){
//		System.out.println("from "+s+" to "+t);
		long result = Integer.MAX_VALUE;
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {

				result = Math.min(result, bucketMin[k]);
//				System.out.println("find bucket "+result);
			} else {

				for(int i = Math.max(s, l); i < Math.min(t, r); ++i) {
					result = Math.min(result, data[i] + bucketAdd[k]);
				}
//				System.out.println("find direct " + result);
			}
		}
		return result;
	}
}