题目描述

Takahashi 有每种 $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 \\leq x \\leq N$ 且 $0 \\leq y \\leq 10^9$。
• 对于第二种查询，$1 \\leq x \\leq N$ 且 $0 \\leq y \\leq 10^4$。
• 对于第三种查询，$1 \\leq x \\leq 10^9$。
• 至少存在一个第三种查询。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出，其中 $\\mathrm{query}_i$ 表示第 $i$ 个查询：

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

输出

输出 $M$ 行，其中 $M$ 是第三种查询的数量。
第 $i$ 行应包含对第 $i$ 个该类查询的响应。

示例输入 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

对于第一个第三种查询，可以选择一张第二种卡牌和三张第三种卡牌，总得分为 $11$，为最大值。
对于第二个第三种查询，可以选择一张第一种卡牌和三张第三种卡牌，总得分为 $19$，为最大值。
对于第三个第三种查询，无法选择四张卡牌，因此应打印 -1。
对于第四个第三种查询，可以选择两张第二种卡牌，总得分为 $4$，为最大值。