让我们先看一个相关的经典算法来帮助你解决这个问题：给定 $n$ 个函数 $f_1(x), f_2(x), \dots, f_n(x)$，其中 $f_i(x) = a_i x + b_i$。当你想要在固定参数 $x$ 下找到所有 $i$ 中 $f_i(x)$ 的最小值时，你只需要在凸包上找到对应的函数即可。

现在给定 $n$ 个函数 $f_1(x), f_2(x), \dots, f_n(x)$，其中 $f_i(x) = (x - a_i)^4 + b_i$。 你需要执行 $m$ 次操作。每次操作属于以下形式之一：

• “1 a b” ($1 \le a \le 50\,000, 1 \le b \le 10^{18}$)：添加一个新函数 $f_{n+1}(x) = (x - a)^4 + b$，然后将 $n$ 更新为 $n + 1$。
• “2 t” ($1 \le t \le n$)：删除函数 $f_t(x)$。保证每个函数不会被删除超过一次。
• “3 x” ($1 \le x \le 50\,000$)：查询 $f_i(x)$ 的最小值，其中 $1 \le i \le n$ 且函数 $f_i(x)$ 尚未被删除。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100\,000$)，分别表示函数的数量和操作的数量。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le 50\,000, 1 \le b_i \le 10^{18}$)，表示第 $i$ 个函数 $f_i(x)$。 接下来的 $m$ 行，每行描述一个上述格式的操作。

输出格式

对于每次查询，输出一行，包含一个整数，表示 $f_i(x)$ 的最小值。当没有任何函数时，输出 “-1”。

样例

输入 1

1
2 8
3 9
6 100
3 4
2 1
3 4
1 1 1
3 4
2 2
2 3
3 4

输出 1

10
116
82
-1