直线加点查最小值（Line Add Get Min）

问题描述

给定 $N$ 条直线，第 $i$ 条为 $y = a_i x + b_i$。请按顺序处理以下 $Q$ 个查询：

• 0 a b：添加一条新直线 $y = a x + b$。
• 1 p：求所有已添加直线在 $x = p$ 处的函数值的最小值，即$$\min_{\text{已添加直线 } y = ax + b} (a \cdot p + b).$$

约束条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $|a_i|, |p| \leq 10^9$
• $|b_i| \leq 10^{18}$

输入格式

$N\ Q$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{N-1}\ b_{N-1}$
$Query_0$
$Query_1$
:
$Query_{Q-1}$

2 8
-1 -1
0 1
1 -1
1 -2
1 0
1 2
0 0 -10
1 -2
1 0
1 2

0
1
-1
-3
-10
-10
-10