题目描述

高桥君有 $N$ 种类的卡牌，每种卡牌各有 $10^{100}$ 张。最初，第 $i$ 种卡牌的得分为 $a_i$，可用张数为 $b_i$。

现在给出 $Q$ 个如下形式的查询，请按顺序处理：

• 1 x y ：将第 $x$ 种卡牌的得分设为 $y$。
• 2 x y ：将第 $x$ 种卡牌的可用张数设为 $y$。
• 3 x ：如果可以选择 $x$ 张卡牌，且满足每种卡牌选择的数量不超过其可用张数，则输出所能获得的最大得分总和，否则输出 $-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$ 类查询的答案。

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

11
19
-1
4

数据范围

1 ≤ N,Q ≤ 2×10^5；0 ≤ a_i ≤ 10^9；0 ≤ b_i ≤ 10^4。第一类查询中 1 ≤ x ≤ N、0 ≤ y ≤ 10^9；第二类查询中 1 ≤ x ≤ N、0 ≤ y ≤ 10^4；第三类查询中 1 ≤ x ≤ 10^9。保证至少有一个第三类查询。