시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 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