Dynamic Convex Hull

First, consider a classical related algorithm. You are given $n$ functions $f_1(x), f_2(x), \dots, f_n(x)$, where $f_i(x)=a_i x+b_i$. To find the minimum value of $f_i(x)$ over all $i$ for a fixed parameter $x$, you only need to find the corresponding function on the convex hull.

Now you are given $n$ functions $f_1(x), f_2(x), \dots, f_n(x)$, where $f_i(x)=(x-a_i)^4+b_i$. You need to perform $m$ operations. Each operation has one of the following forms:

• "1 $a$ $b$" ($1 \leq a \leq 50\,000$, $1 \leq b \leq 10^{18}$): Add a new function $f_{n+1}(x)=(x-a)^4+b$, then change $n$ into $n+1$.
• "2 $t$" ($1 \leq t \leq n$): Delete the function $f_t(x)$. Each function is deleted at most once.
• "3 $x$" ($1 \leq x \leq 50\,000$): Query the minimum value of $f_i(x)$ over all $1 \leq i \leq n$ whose function $f_i(x)$ has not been deleted yet.

The first line contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. Each test case is described as follows.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 100\,000$), the number of functions and the number of operations.

Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i \leq 50\,000$, $1 \leq b_i \leq 10^{18}$), which define the $i$-th function $f_i(x)$.

Each of the next $m$ lines describes one operation in the format shown above.

For each query, print a single line containing the minimum value of $f_i(x)$. If there are no functions, print "-1" instead.