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

Source: aizu | Difficulty: UNKNOWN_DIFFICULTY


Solutions: