問題文

高橋君は $N$ 種類のカードを $10^{100}$ 枚ずつ持っています。はじめ、$i$ 種類目のカードの得点は $a_i$ で、使用可能枚数は $b_i$ です。

以下の形式のクエリが $Q$ 個与えられるので、順に処理してください。

• 1 x y : $x$ 種類目のカードの得点を $y$ に設定
• 2 x y : $x$ 種類目のカードの使用可能枚数を $y$ に設定
• 3 x : 次の条件を満たすように $x$ 枚のカードを選ぶことができるならば選ばれたカードの得点の総和の最大値を、そうでなければ -1 を出力
  • どの種類のカードもその使用可能枚数を超えて選ばれない

制約

• $1 \\leq N,Q \\leq 2 \\times 10^5$
• $0 \\leq a_i \\leq 10^9$
• $0 \\leq b_i \\leq 10^4$
• $1$ 種類目のクエリにおいて $1 \\leq x \\leq N, 0 \\leq y \\leq 10^9$
• $2$ 種類目のクエリにおいて $1 \\leq x \\leq N, 0 \\leq y \\leq 10^4$
• $3$ 種類目のクエリにおいて $1 \\leq x \\leq 10^9$
• $3$ 種類目のクエリが $1$ 個以上含まれる
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ただし、$\\mathrm{query}_i$ で $i$ 番目のクエリを表す。

$N$ $a_1$ $b_1$ $\\vdots$ $a_N$ $b_N$ $Q$ $\\mathrm{query}_1$ $\\vdots$ $\\mathrm{query}_Q$

出力

$3$ 種類目のクエリの個数を $M$ とする。$M$ 行出力をせよ。
$i$ 行目には $i$ 番目の $3$ 種類目のクエリに対する出力をせよ。

入力例 1

3
1 1
2 2
3 3
7
3 4
1 1 10
3 4
2 1 0
2 3 0
3 4
3 2

出力例 1

11
19
-1
4

$1$ 番目の $3$ 種類目のクエリでは、$2$ 種類目のカードを $1$ 枚、$3$ 種類目のカードを $3$ 枚選ぶことで得点の総和が $11$ となり、これが最大です。
$2$ 番目の $3$ 種類目のクエリでは、$1$ 種類目のカードを $1$ 枚、$3$ 種類目のカードを $3$ 枚選ぶことで得点の総和が $19$ となり、これが最大です。
$3$ 番目の $3$ 種類目のクエリでは、$4$ 枚のカードを選ぶことができないため出力は -1 となります。
$4$ 番目の $3$ 種類目のクエリでは、$2$ 種類目のカードを $2$ 枚選ぶことで得点の総和が $4$ となり、これが最大です。