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 <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

constexpr int si = 300;
constexpr ll inf = 1e18;

class SqrtDecomposition{
private:
    int N,K;
    vec<ll> bucket;
    vec<ll> lazy;
    vvec<ll> Amin,Bmin;
    vvec<P<ll,ll>> AsubB;
    vec<ll> A,B;
public:
    SqrtDecomposition(int N,vec<ll>& a,vec<ll>& b):N(N){
        //K個のbucketがある
        K = (N+si-1)/si;
        A = B = vec<ll>(K*si,inf);
        bucket = vec<ll>(K,inf);
        lazy = vec<ll>(K,0);
        Amin = Bmin = vvec<ll>(K);
        AsubB = vvec<P<ll,ll>>(K);
        for(int i=0;i<N;i++){
            A[i] = a[i];
            B[i] = b[i];
        }
        for(int k=0;k<K;k++){
            Amin[k] = Bmin[k] = vec<ll>(si,inf);
            AsubB[k] = vec<P<ll,ll>>(si);
            bucketupdate(k);
        }
    }

    void bucketupdate(int k){
        int l = k*si,r = (k+1)*si;
        for(int i=l;i<r;i++){
            A[i] += lazy[k];
            AsubB[k][i-l] = {A[i]-B[i],i};
        }
        lazy[k] = 0;
        sort(AsubB[k].begin(),AsubB[k].end());
        for(int i=0;i<si;i++){
            int id = AsubB[k][i].second;
            Bmin[k][i] = min(B[id],(i!=0? Bmin[k][i-1]:inf));
        }
        for(int i=si-1;i>=0;i--){
            int id = AsubB[k][i].second;
            Amin[k][i] = min(A[id],(i!=si-1? Amin[k][i+1]:inf));
        }
        int id = lower_bound(AsubB[k].begin(),AsubB[k].end(),P<ll,ll>(0,-inf))-AsubB[k].begin();
        bucket[k] = min((id!=0? Bmin[k][id-1]:inf),(id!=si? Amin[k][id]:inf));
    }

    void update(int l,int r,ll x){
        for(int k=0;k<K;k++){
            int lb = k*si,rb = (k+1)*si;
            if(rb<=l || r<=lb) continue;
            if(l<=lb && rb<=r){
                lazy[k] += x;
                int id = lower_bound(AsubB[k].begin(),AsubB[k].end(),P<ll,ll>(-lazy[k],-inf))-AsubB[k].begin();
                bucket[k] = min((id!=0? Bmin[k][id-1]:inf),(id!=si? Amin[k][id]+lazy[k]:inf));
            }
            else{
                for(int i=max(l,lb);i<min(r,rb);i++) A[i] += x;
                bucketupdate(k);
            }
        }
    }
    
    ll query(int l,int r){
        ll res = inf;
        for(int k=0;k<K;k++){
            int lb = k*si,rb = (k+1)*si;
            if(rb<=l || r<=lb) continue;
            if(l<=lb && rb<=r) res = min(res,bucket[k]);
            else{
                for(int i=max(l,lb);i<min(r,rb);i++) res = min(res,max(A[i]+lazy[k],B[i]));
            }
        }
        return res;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q;
    cin >> N >> Q;
    vec<ll> A(N),B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }
    SqrtDecomposition dcmp(N,A,B);
    for(int q=0;q<Q;q++){
        int t;
        cin >> t;
        if(t==1){
            int l,r; ll x;
            cin >> l >> r >> x;
            l--; r--;
            dcmp.update(l,r+1,x);
        }else{
            int l,r;
            cin >> l >> r;
            l--; r--;
            cout << dcmp.query(l,r+1) << "\n";
        }
    }
}
