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 <vector>
#include <utility>
#include <algorithm>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

llint n, Q;
llint a[100005], b[100005];
llint a2[100005], b2[100005], dif[100005];
llint Amin[100005], Bmin[100005];
llint add[100005];
const int B = 300;

void calc(llint l, llint r, llint x)
{
	llint bid = l/B, L = bid*B, R = min(n, (bid+1)*B);
	for(int i = l; i <= r; i++) a[i] += x;
	for(int i = L; i < R; i++) a[i] += add[bid];
	add[bid] = 0;
	
	vector<P> vec;
	for(int i = L; i < R; i++){
		vec.push_back(P(a[i]-b[i], i));
	}
	sort(vec.begin(), vec.end());
	
	for(int i = 0; i < vec.size(); i++){
		llint p = L + i;
		dif[p] = vec[i].first;
		a2[p] = a[vec[i].second], b2[p] = b[vec[i].second];
	}
	llint mn = inf;
	for(int i = L; i < R; i++){
		mn = min(mn, b2[i]);
		Bmin[i] = mn;
	}
	mn = inf;
	for(int i = R-1; i >= L; i--){
		mn = min(mn, a2[i]);
		Amin[i] = mn;
	}
}

llint get(llint l, llint r)
{
	llint ret = inf, bid = l/B;
	for(int i = l; i <= r; i++){
		ret = min(ret, max(a[i]+add[bid], b[i]));
	}
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> Q;
	for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
	for(int i = 0; i < n/B; i++) calc(i*B, (i+1)*B-1, 0);
	calc(n/B*B, n-1, 0);
	
	/*for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << b[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << a2[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << b2[i] << " "; cout << endl;
	for(int i = 0; i < n; i++) cout << dif[i] << " "; cout << endl;
	for(int i = 0; i < n/B; i++) cout << add[i] << " "; cout << endl;*/
	
	llint t, l, r, x;
	for(int q = 1; q <= Q; q++){
		//cout << "Q " << q << endl;
		cin >> t >> l >> r;
		l--, r--;
		llint L = (l+B-1)/B*B, R = r/B*B;
		if(t == 1){
			cin >> x;
			if(l/B == r/B){
				calc(l, r, x);
				continue;
			}
			calc(l, L-1, x);
			calc(R, r, x);
			for(int i = L/B; i < R/B; i++) add[i] += x;
		}
		else{
			llint ans = inf;
			if(l/B == r/B){
				cout << get(l, r) << endl;
				continue;
			}
			ans = min(ans, get(l, L-1));
			ans = min(ans, get(R, r));
			for(int i = L/B; i < R/B; i++){
				llint pos = lower_bound(dif+i*B, dif+(i+1)*B, -add[i]) - dif;
				if(pos < n && pos/B == i) ans = min(ans, Amin[pos]+add[i]);
				if(pos > 0 && (pos-1)/B == i) ans = min(ans, Bmin[pos-1]);
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}
