题目描述
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
输入格式
见题面
输出格式
见题面