直线加查询最小值

【题目描述】

有 $N$ 条直线 $y = a_i x + b_i$。需要处理 $Q$ 个查询。

• 0 $a$ $b$：添加一条直线 $y = ax + b$。
• 1 $p$：求 $x = p$ 处的 $y$ 的最小值。

【输入】

第一行包含两个整数 $N$ $Q$。

接下来 $N$ 行，第 $i$ 行包含两个整数 $a_i$ $b_i$，表示初始的第 $i$ 条直线 $y = a_i x + b_i$。

接下来 $Q$ 行，第 $j$ 行描述第 $j$ 个查询：0 $a$ $b$ 表示添加直线，1 $p$ 表示询问。

$N$ $Q$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{N-1}$ $b_{N-1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对每个 1 $p$ 查询，输出一行一个整数，表示当前所有直线在 $x = p$ 处的 $y$ 的最小值。

【输入样例】

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

【数据范围】

• $1 \leq N, Q \leq 200000$
• $|a_i|, |p| \leq 1000000000$
• $|b_i| \leq 1000000000000000000$

【来源】

Library Checker（yosupo06） line_add_get_min