Description

Alice 和 Bob 又开始玩游戏了。这次的游戏和石子无关，而是一个纸牌游戏。

桌面上有 $n$ 张牌，每张牌上写有两个整数（一个表示红色，一个表示蓝色）。每一轮开始时，会给出两个整数 $L$ 和 $R$。Alice 需要选择一个整数 $x$，满足 $L \le x \le R$，并将她的选择告诉 Bob。在得知 $x$ 后，Bob 会从桌面上选择一张牌。本轮得分等于 $rx + b$，其中 $r$ 表示所选牌上的红色整数，$b$ 表示该牌上的蓝色整数。

Alice 和 Bob 都可以在做出决策前自由查看桌面上的所有牌及其整数。

为了让游戏更加有趣，在某一轮前可以进行如下操作：

• 向桌面上加入一张写有红色和蓝色整数的新牌。
• 移除桌面上的一张牌。

Alice 希望每一轮都最大化得分，而 Bob 则希望最小化得分。如果两人都采取最优策略，你能求出每一轮的最终得分么？

Input Format

输入包含多组测试数据。第一行为一个整数 $T$，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$（$1 \le n \le 5 \times 10^4$）和 $q$（$1 \le q \le 5 \times 10^4$），表示初始在桌面上的牌数和操作数。

接下来的 $n$ 行，每行包含两个整数 $r_i$ 和 $b_i$（$-10^9 \le r_i, b_i \le 10^9$），表示初始时有一张牌，其红色数为 $r_i$、蓝色数为 $b_i$。

接下来的 $q$ 行，每行包含三个整数 $op$（$0 \le op \le 2$）、$a$、$b$（$-10^9 \le a, b \le 10^9$）。

• 若 $op = 0$，表示你需要计算该回合的最终得分，给定 $L = a$ 和 $R = b$。保证此时 $a \le b$。
• 若 $op = 1$，表示将一张红色数为 $a$，蓝色数为 $b$ 的新牌放到桌面上。
• 若 $op = 2$，表示要移除一张红色数为 $a$，蓝色数为 $b$ 的牌。保证这张牌存在于桌面上。如果有多张满足的牌，只移除一张即可。

保证所有测试数据中 $n$ 和 $q$ 的总和不超过 $2 \times 10^5$。

请注意，本题输入输出数据量较大，建议使用更快的输入输出方式。例如，C++ 中可以使用 scanf/printf 替代 cin/cout。

Output Format

对于每个 $op = 0$ 的操作，输出一行，表示该回合的最终得分。

2
2 7
-1 2
2 3
0 -1 1
2 -1 2
0 -1 1
2 2 3
1 1 2
1 -2 -1
0 -1 1
2 3
1 1
1 1
0 1 3
2 1 1
0 1 3

2
5
1
4
4

Hint

由 ChatGPT 5 翻译