Range Min of Max Query

整数の組の列(a_1,b_1), (a_2,b_2),..,(a_N,b_N)が与えられます。

二種類のクエリを処理してください。

一種類目のクエリでは、a_L,a_{L+1},..,a_RにXを加算します。

二種類目のクエリでは、max(a_L,b_L),max(a_{L+1},b_{L+1}),..,max(a_R,b_R)の最小値を求めます。

入力

N Q
a_1 b_1
a_2 b_2
:
a_N b_N
query_1
query_2
:
query_Q

i番目のクエリが一種類目のクエリの場合、query_iは1 L_i R_i X_iとなります。

i番目のクエリが二種類目のクエリの場合、query_iは2 L_i R_iとなります。

出力

ans_1
ans_2
:
ans_k

二種類目のクエリに対する答えを順に出力せよ。

制約

• 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

入力例

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