問題文

色のついたスライムが左右一列に並んでおり、左から順に攻撃力が $A_1$ のスライムが $B_1$ 体、攻撃力が $A_2$ のスライムが $B_2$ 体、......、攻撃力が $A_N$ のスライムが $B_N$ 体並んでいます。

スライムは、連続する $1$ 体以上のスライム同士でチームを組むことができます。
また、チームの総合力はチームのスライムの攻撃力の総和で定義されます。

クエリが $Q$ 個与えられるため、それぞれのクエリを順に処理してください。

• 1 x y : 左から $x$ 番目のスライムの攻撃力を $y$ に変更する。
• 2 l r : 左から $l$ から $r$ 番目のスライムの中でチームを組んだとき、チームの総合力としてあり得る最大値を出力する。

制約

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $| A_i | \leq 10^5$
• $1 \leq B_i \leq 10^5$
• $1 \leq x \leq \sum_{i = 1}^{N} B_i$
• $| y | \leq 10^5$
• $1 \leq l \leq r \leq \sum_{i = 1}^{N} B_i$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ 
$A_1$ $B_1$  
$A_2$ $B_2$  
$\vdots$

$A_N$ $B_N$
$Q$
query $1$  
query $2$  
$\vdots$

query $Q$

各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

$1$ $x$ $y$

$2$ $l$ $r$

出力

$2$ のクエリの個数を $q$ として、$q$ 行出力せよ。
$j$ $(1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

サンプル

8
2 1
-7 2
3 2
-5 1
5 1
-3 2
7 2
-2 1
7
2 1 12
1 10 -2
2 1 12
2 1 10
1 7 10
2 1 10
2 2 3

14
7
6
11
-7