동적 볼록 껍질

먼저 관련된 고전 알고리즘을 살펴보자. $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 \leq a \leq 50\,000$, $1 \leq b \leq 10^{18}$): 새로운 함수 $f_{n+1}(x)=(x-a)^4+b$를 추가한 뒤 $n$을 $n+1$로 바꾼다.
• "2 $t$" ($1 \leq t \leq n$): 함수 $f_t(x)$를 삭제한다. 각 함수는 두 번 이상 삭제되지 않는다고 보장된다.
• "3 $x$" ($1 \leq x \leq 50\,000$): $1 \leq i \leq n$이고 아직 삭제되지 않은 함수 $f_i(x)$ 중에서 최솟값을 구한다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \leq T \leq 5$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에 함수의 개수 $n$과 연산의 개수 $m$ ($1 \leq n, m \leq 100\,000$)이 주어진다.

이어서 $n$개의 줄에 각각 $i$번째 함수 $f_i(x)$를 정하는 정수 $a_i$와 $b_i$ ($1 \leq a_i \leq 50\,000$, $1 \leq b_i \leq 10^{18}$)가 주어진다.

다음 $m$개의 줄에는 연산이 하나씩 주어진다. 각 연산의 형식은 위와 같다.

각 질의에 대해 $f_i(x)$의 최솟값을 한 줄에 출력한다. 함수가 하나도 없으면 "-1"을 출력한다.