Range Min of Max Query

Given a sequence of integer pairs (a_1, b_1), (a_2, b_2), .., (a_N, b_N).

Handle two types of queries.

The first type of query adds X to a_L, a_ {L + 1}, .., a_R.

The second type of query finds the minimum values ​​of max (a_L, b_L), max (a_ {L + 1}, b_ {L + 1}), .., max (a_R, b_R).

input


N Q
a_1 b_1
a_2 b_2
::
a_N b_N
query_1_1
query_2
::
query_Q


If the i-th query is the first type of query, query_i will be 1 L_i R_i X_i.

If the i-th query is the second type of query, query_i will be 2 L_i R_i.

output


ans_1
ans_2
::
ans_k


Output the answers to the second type of query in order.

Constraint

* 1 \ leq N, Q \ leq 10 ^ 5
* 1 \ leq a_i, b_i \ leq 10 ^ 9
* 1 \ leq L_i \ leq R_i \ leq N
* -10 ^ 9 \ leq X_i \ leq 10 ^ 9



Input example


6 6
8 1
6 1
9 4
1 5
twenty one
14
2 1 3
1 1 3 3
2 1 3
2 4 6
1 4 6 3
2 4 6


Output example


6
9
2
Four






Example

Input

6 6
8 1
6 1
9 4
1 5
2 1
1 4
2 1 3
1 1 3 3
2 1 3
2 4 6
1 4 6 3
2 4 6


Output

6
9
2
4
#include<iostream>
#include<cstddef>
#include<cstdint>
#include<vector>
#include<algorithm>
using usize=std::size_t;
using i64 = std::int_fast64_t;

int main(){
static constexpr i64 Inf=std::numeric_limits<i64>::max()/2;
  static constexpr usize B=300;

std::ios::sync_with_stdio(false);
std::cin.tie(0);

  struct block_t{
    i64 x;
    std::vector<i64> a,b;
    std::vector<i64> bma,ra,rb;

    block_t():x(0),a(B,0),b(B,Inf),bma(B),ra(B+1),rb(B+1){}

    void build(){
      std::vector<usize> idx(B);
      for(usize i=0;i<B;++i)idx[i]=i;
      std::sort(idx.begin(),idx.end(),[&](usize l_,usize r_){
        return b[l_]-a[l_]<b[r_]-a[r_];
      });
      for(usize i=0;i<B;++i){
        bma[i]=b[idx[i]]-a[idx[i]];
      }
      ra[0]=Inf;
      for(usize i=0;i<B;++i){
        ra[i+1]=std::min(ra[i],a[idx[i]]);
      }
      rb[B]=Inf;
      for(usize i=B;i!=0;--i){
        rb[i-1]=std::min(rb[i],b[idx[i-1]]);
      }
    }

    void add_all(const i64 x_){
      x+=x_;
    }
    i64 get_all(){
      const usize i = std::lower_bound(bma.cbegin(),bma.cend(),x)-bma.cbegin();
      return std::min(ra[i]+x,rb[i]);
    }
    i64 get_part(const usize l,const usize r){
      i64 ret=Inf;
      for(usize i=l;i<r;++i){
        ret=std::min(ret,std::max(a[i]+x,b[i]));
      }
      return ret;
    }
    void add_part(const usize l,const usize r,const i64 x_){
      for(usize i=l;i<r;++i){
        a[i]+=x_;
      }
      build();
    }
  };


  usize n,q;
  std::cin>>n>>q;

  std::vector<block_t> sqd(n/B+1);

  for(usize i=0;i<n;++i){
    std::cin>>sqd[i/B].a[i%B]>>sqd[i/B].b[i%B];
  }
  for(auto &e:sqd)e.build();


  for(usize i=0;i<q;++i){
    usize t,l,r;
    std::cin>>t>>l>>r;
    l-=1;
    
    if(t==1){
      i64 x;
      std::cin>>x;
      if(l/B==r/B){
        sqd[l/B].add_part(l%B,r%B,x);
      }else{
        sqd[l/B].add_part(l%B,B,x);
        for(usize i=l/B+1;i<r/B;++i){
          sqd[i].add_all(x);
        }
        sqd[r/B].add_part(0,r%B,x);
      }
    }else{
      i64 ans=Inf;
      if(l/B==r/B){
        ans=sqd[l/B].get_part(l%B,r%B);
      }else{
        ans=std::min(ans,sqd[l/B].get_part(l%B,B));
        for(usize i=l/B+1;i<r/B;++i){
          ans=std::min(ans,sqd[i].get_all());
        }
        ans=std::min(ans,sqd[r/B].get_part(0,r%B));
      }
      std::cout<<ans<<std::endl;
    }
  }
}

/*

a+x>b    x > b-a
a+x <=b  x <= b-a

*/
