Alice 和 Bob 又在玩游戏了。这个游戏和石头无关，实际上是一个卡牌游戏。

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

Alice 和 Bob 在做出决定前都可以自由查看桌上的卡牌以及上面写的整数。

为了让游戏更有趣，在某些轮次之前可以进行一些更改。有两种可能的更改：

1. 在桌上增加一张写有红色整数和蓝色整数的卡牌。
2. 从桌上移除一张卡牌。

Alice 希望最大化每一轮的得分，而 Bob 希望最小化它。如果他们都采取最优策略，你能求出每一轮的最终得分吗？

输入格式

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

第一行包含两个整数 $n$ ($1 \le n \le 5 \times 10^4$) 和 $q$ ($1 \le q \le 5 \times 10^4$)，分别表示初始时桌上的卡牌数量和操作次数。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $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$。

我们提醒您，本题涉及大量 I/O 操作，建议使用较快的 I/O 方法。例如，在 C++ 中可以使用 scanf/printf 代替 cin/cout。

输出格式

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

样例

输入 1

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

输出 1

2
5
1
4
4