线段加查询最小值

【题目描述】

平面上有 $N$ 条线段 $y = a_i x + b_i$（其中 $x \in [l_i, r_i)$）。请依次处理 $Q$ 个查询。

• 0 $l$ $r$ $a$ $b$：添加一条线段 $y = ax + b$（其中 $x \in [l, r)$）
• 1 $p$：求 $x = p$ 处 $y$ 的最小值。若不存在这样的 $y$，输出 INFINITY。

【输入】

输入格式如下：

$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}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对每个 1 $p$ 查询，输出一行一个整数，表示 $x = p$ 处 $y$ 的最小值。若不存在这样的 $y$，输出 INFINITY。

【输入样例】

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

【输入样例2】

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

【输出样例2】

INFINITY
0

【数据范围】

• $1 \leq N, Q \leq 200000$
• $-1000000000 \leq l_i \lt r_i \leq 1000000000$
• $|a_i|, |p| \leq 1000000000$
• $|b_i| \leq 1000000000000000000$

【来源】

Library Checker（yosupo06） segment_add_get_min