题目背景

战至中途，蓝紫色天空瞬间变为黑压压一片，噬神者身上一些紫色外壳开始脱落，化为更小的蟒蛇，这些小家伙从出现开始便不要命的向你冲过来，刚清理掉这些小家伙，迷雾中忽然涌现出一张血盆大口，噬神者正向你冲击而来......

题目描述

现给定一个有 $n$ 段的分段函数，每一段可能是一个一次函数或者一个二次函数，并有 $q$ 次询问，每次询问 $x=k$ 时 $y$ 的取值或是 $y=k$ 与函数有多少个交点。

输入格式

第一行两个用空格分隔的整数 $n,q$，表示函数段数与询问次数。

从第 $2$ 行到 $n+1$ 行，先给出 $l_i$ $r_i$，表示这个分段函数对应的取值范围为 $(l_i,r_i]$（保证 $l_1=0$，$\forall i\in [1,n-1],r_i=l_{i+1}$）。然后读入有以下两种情况：

• $1$ $k$ $b$，表示这个区间内是 $y=kx+b$ 的一个一次函数（保证 $k\ne 0$）。
• $2$ $a$ $b$ $c$，表示这个区间内是 $y=ax^2+bx+c$ 的二次函数（保证 $a\ne 0$）。

从第 $n+2$ 行到第 $n+q+1$ 行，每行两个用空格分隔的整数 $op,k$：

• 若 $op=1$ ，表示求出当 $x=k$ 时 $y$ 的值（保证 $k\in (0,r_n]$）。
• 若 $op=2$ ，表示求出直线 $y=k$ 在 $(0,r_n]$ 范围内与整个分段函数有几个交点。

输出格式

一共 $q$ 行，每行一个整数表示对于每个询问的答案。

3 4
0 3 1 1 2
3 6 2 1 -2 1
6 10 1 1 0
1 4
2 5
2 114514
2 2

9
2
0
0

6 8
0 4 2 1 -4 0 
4 6 1 2 -10 
6 11 1 1 -19 
11 19 2 -1 -30 559 
19 29 1 1 -58 
29 38 1 1 -68 
1 11
2 4
2 -1
1 21
2 -5
2 2
1 34
2 1

-8
1
4
-37
1
2
-34
2

提示

【样例解释 #1】

三段函数分别为 $y=x+2$，$y=x^2-2x+1$，$y=x$。

对于当 $x=4$ 时套入第二段函数可以得到结果为 $9$。

而直线 $y=5$ 只与第一段与第二段函数相交，并且各只有一个交点，所以结果为 $2$。

显而易见，第三个询问对应的直线不与函数相交。

第四个询问虽然与第一段函数交于 $x=0$ 的位置，但 $0$ 不在该函数区间内，故舍去。

---

【数据范围】

本题采用捆绑测试。

Subtask	Score	$n,q\le$	limit
$1$	$10$	$100$	无
$2$	$15$	$10^3$	$r_n\le 5\times 10^3$
$3$	$20$	$2\times 10^5$	不存在询问 $2$
$4$	$25$		不存在二次函数
$5$	$30$		无

对于 $100\%$ 的数据，$1\le n,q\le 2\times 10^5$，$0\le l_i,r_i\le10^9$，$\forall i\in [1,n],r_i>l_i$ 。

所有的函数系数均在 $64$ 位有符号整型变量存储范围内，并且运算结果与每个函数式中任何一项的最大值与最小值不会超过 $64$ 位有符号整型变量存储范围。所有询问参数均在 $32$ 位有符号整型变量范围内。

（即 $-4\times 10^{18}\le k,a,b,c\le 4\times 10^{18}$，$-10^9\le x\le 10^9$）

---

【提示】

采用浮点数据时建议使用 long double，避免产生精度问题。

upd：添加一组 hack 数据，未通过会显示为“Unaccepted 100pts”。