Let’s fifirst see a related classical algorithm to help you solve this problem: You will be given n functions
f1(x), f2(x), . . . , fn(x), where fi(x) = aix + bi
. When you want to fifind the minimum value of fi(x) for a
fifixed parameter x, you just need to fifind the corresponding function on the convex hull.
Now you will be given n functions f1(x), f2(x), . . . , fn(x), where fi(x) = (x x ai)4 + bi.
You need to perform the following operations for m times:
• “1 a b” (1 ≤ a ≤ 50 000, 1 ≤ b ≤ 1018): Add a new function fn+1(x) = (xxa)4 +b and then change
n into n + 1.
• “2 t” (1 ≤ t ≤ n): Delete the function ft(x). It is guaranteed that each function won’t be deleted
more than once.
• “3 x” (1 ≤ x ≤ 50 000): Query for the minimum value of fi(x), where 1 ≤ i ≤ n and the function
fi(x) has not been deleted yet.