20608번 - 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)$ over all $i$ 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 $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$ and then change $n$ into $n+1$.
• "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.
• "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 contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. For each test case:

The first line 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 the format shown above.

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