Range Min of Max Query

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

inputFormat

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.

outputFormat

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

样例

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

6
9
2
4

</p>