当前没有测试数据。

G - 平衡更新查询

得分：$600$分

问题描述

Takahashi有每种卡片 $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$ 个这类查询的响应。

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

对于第一个第三种查询，你可以选择一张第二种卡片和三张第三种卡片，总得分是 $11$，这是最多的。
对于第二个这类查询，你可以选择一张第一种卡片和三张第三种卡片，总得分是 $19$，这是最多的。
对于第三个这类查询，你无法选择四张卡片，因此应该输出 -1。
对于第四个这类查询，你可以选择两张第二种卡片，总得分是 $4$，这是最多的。