Dynamic Convex Hull

Let's first see a related classical algorithm to help you solve this problem: You will be given $n$ functions $f_1(x),f_2(x),\dots,f_n(x)$, where $f_i(x)=a_ix+b_i$. When you want to find the minimum value of $f_i(x)$ for a fixed parameter $x$, you just need to find the corresponding function on the convex hull.

Now you will be 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 the following operations for $m$ times:

· "$\texttt{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$ and then change $n$ into $n+1$.

· "$\texttt{2 t}$" ($1\leq t\leq n$): Delete the function $f_{t}(x)$. It is guaranteed that each function won't be deleted more than once.

· "$\texttt{3 x}$" ($1\leq x\leq 50\,000$): Query for the minimum value of $f_i(x)$, where $1\leq i\leq n$ and the function $f_i(x)$ has not been deleted yet.

The first line of the input contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases.

For each case, the first line of the input contains two integers $n$ and $m$ ($1 \leq n ,m\leq 100\,000$), denoting 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}$), denoting the $i$-th function $f_i(x)$.

Each of the next $m$ lines describes an operation in formats described in the statement above.

For each query, print a single line containing an integer, denoting the minimum value of $f_i(x)$. Note that when there is no functions, print "$\texttt{-1}$" instead.

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

10
116
82
-1

2020 Multi-University Training Contest 2