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;
using ll=long long;

#include <vector>
#include <functional>

template <typename T,typename E>
struct LazySegmentTree{
   using F=std::function<T(T,T)>;
   using G=std::function<T(T,E,int,int)>;
   using H=std::function<E(E,E)>;

   int n;
   std::vector<T> dat;
   std::vector<E> laz;
   const F f;
   const G g;
   const H h;
   const T d1;
   const E d0;

   LazySegmentTree(int n_,const F f,const G g,const H h,const T d1,const E d0):f(f),g(g),h(h),d1(d1),d0(d0)
   {
      n=1;
      while(n_>n) n<<=1;
      dat.assign(2*n,d1);
      laz.assign(2*n,d0);
   }

   void set(int k,const T &x){
      dat[k+n]=x;
   }
   void build(){
      for(int k=n-1;k>0;--k) dat[k]=f(dat[2*k],dat[2*k+1]);
   }
   void eval(int k,int l,int r){
      if(laz[k]==d0) return;
      dat[k]=g(dat[k],laz[k],l,r);
      if(k<n){
         laz[2*k]=h(laz[2*k],laz[k]);
         laz[2*k+1]=h(laz[2*k+1],laz[k]);
      }
      laz[k]=d0;
   }
   void update(int a,int b,E x,int k=1,int l=0,int r=-1){
      if(r<0) r=n;
      eval(k,l,r);
      if(r<=a||b<=l) return;
      if(a<=l&&r<=b){
         laz[k]=h(laz[k],x);
         eval(k,l,r);
      }
      else{
         update(a,b,x,2*k,l,(l+r)/2);
         update(a,b,x,2*k+1,(l+r)/2,r);
         dat[k]=f(dat[2*k],dat[2*k+1]);
      }
   }
   T query(int a,int b,int k=1,int l=0,int r=-1){
      if(r<0) r=n;
      eval(k,l,r);
      if(r<=a||b<=l) return d1;
      if(a<=l&&r<=b) return dat[k];
      T vl=query(a,b,2*k,l,(l+r)/2);
      T vr=query(a,b,2*k+1,(l+r)/2,r);
      return f(vl,vr);
   }
};

/*

-RMinimumQ and RUpdateQ
f=[](T x,T y){ return min(x,y); };
g=[](T x,E y,int l,int r){ return y; };
h=[](E x,E y){ return y; };

-RSumQ and RAddQ
f=[](T x,T y){ return x+y; };
g=[](T x,E y,int l,int r){ return x+(r-l)*y; };
h=[](E x,E y){ return x+y; };

-RMinimumQ and RAddQ
f=[](T x,T y){ return min(x,y); };
g=[](T x,E y,int l,int r){ return x+y; };
h=[](E x,E y){ return x+y; };

-RSumQ and RUpdateQ
f=[](T x,T y){ return x+y; };
g=[](T x,E y,int l,int r){ return (r-l)*y; };
h=[](E x,E y){ return y; };

*/

int main(){
   int n,q;
   cin>>n>>q;
   using T=ll;
   using E=ll;
   auto f=[](T x,T y){ return min(x,y); };
   auto g=[](T x,E y,int l,int r){ return x+y; };
   auto h=[](E x,E y){ return x+y; };
   LazySegmentTree<ll,ll> seg(n,f,g,h,INT_MAX,0);
   for(int i=0;i<n;++i) seg.set(i,0);
   seg.build();
   for(int i=0;i<q;++i){
      int com;
      cin>>com;
      int s,t,x;
      cin>>s>>t;
      if(com==0){
         cin>>x;
         seg.update(s,t+1,x);
      }
      else{
         cout<<seg.query(s,t+1)<<endl;
      }
   }
}