线段加 & 值查询最小值（Segment Add Get Min）

问题描述

有 $N$ 条线段，第 $i$ 条线段定义为函数 $y = a_i x + b_i$，其中定义域为区间 $x \in [l_i, r_i)$。
处理 $Q$ 个查询：

• 0 l r a b：添加一条新线段 $y = a x + b$，定义域为 $x \in [l, r)$。
• 1 p：查询在横坐标 $x = p$ 处所有已添加线段中 $y$ 的最小值；若无任何线段覆盖 $p$，输出 INFINITY。

约束条件

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

输入

$N\ Q$
$l_0\ r_0\ a_0\ b_0$
$l_1\ r_1\ a_1\ b_1$
:
$l_{N-1}\ r_{N-1}\ a_{N-1}\ b_{N-1}$
Query₀
Query₁
:
Query$_{Q-1}$

2 8
-3 3 -1 -1
0 7 0 1
1 -1
1 -2
1 0
1 2
0 -4 2 0 -10
1 -2
1 0
1 2

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

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

INFINITY
0