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>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}


struct LazySegmentTree {
  int N;
  vector<ll> node,lazy;
  vector<bool> delay;
  LazySegmentTree(int n_){
    N = 1; while (N < n_) N *= 2;
    node.assign(2*N-1, 0); // 暫定的な最小値
    lazy.assign(2*N-1, 0); // 一様に加えるやつ
    delay.assign(2*N-1, false); // 遅延しているかどうか
  }

  // 遅延評価
  void eval(int k,int l,int r){
    if (!delay[k]) return;
    node[k] += lazy[k];
    if (r-l > 1){
      // 葉ノードでなければlazyを伝播する
      lazy[2*k+1] += lazy[k]; delay[2*k+1] = true;
      lazy[2*k+2] += lazy[k]; delay[2*k+2] = true;
    }
    lazy[k] = 0; delay[k] = false;
  }

  // [a,b) に各々 x を加える。見ているノード k が [l,r)
  void add(int a,int b,ll x,int k=0,int l=0,int r=-1){
    if (r == -1) r = N;
    eval(k,l,r);
    if (b <= l || r <= a) return;
    if (a <= l && r <= b){
      lazy[k] += x; delay[k] = true;
      eval(k,l,r);
      return;
    }
    add(a, b, x, 2*k+1, l, (l+r)/2);
    add(a, b, x, 2*k+2, (l+r)/2, r);
    node[k] = min(node[2*k+1], node[2*k+2]);
  }

  // [a,b) の最小値を返す。見ているノード k が [l,r)
  ll getmin(int a,int b,int k=0,int l=0,int r=-1){
    if (r == -1) r = N;
    eval(k,l,r);
    if (b <= l || r <= a) return numeric_limits<ll>::max();
    if (a <= l && r <= b) return node[k];
    ll vl = getmin(a, b, 2*k+1, l, (l+r)/2);
    ll vr = getmin(a, b, 2*k+2, (l+r)/2, r);
    return min(vl,vr);
  }
};

int main() {
  int N,Q; cin >>N >>Q;
  LazySegmentTree lst(N);
  rep(qq, Q){
    int query; cin >>query;
    int s,t; cin >>s >>t; t++;
    if (query == 0){
      ll x; cin >>x;
      lst.add(s,t,x);
    }else{
      cout <<lst.getmin(s,t) <<endl;
    }
  }
}