Background

Midway through the battle, the blue-purple sky suddenly turned into a vast black mass. Some purple shells on the God Devourer began to fall off, turning into smaller pythons. From the moment they appeared, these little guys charged at you recklessly. After you had just cleared them out, a bloody huge mouth suddenly emerged from the mist, as the God Devourer rushed toward you......

Problem Description

You are given a piecewise function with $n$ segments. Each segment may be a linear function or a quadratic function. There are $q$ queries. Each query asks either for the value of $y$ when $x=k$, or for how many intersection points the line $y=k$ has with the function.

Input Format

The first line contains two integers $n,q$ separated by spaces, representing the number of segments and the number of queries.

From line $2$ to line $n+1$, first read $l_i$ and $r_i$, meaning that the domain of this segment is $(l_i,r_i]$ (it is guaranteed that $l_1=0$, and $\forall i\in [1,n-1],r_i=l_{i+1}$). Then read one of the following two cases:

• $1$ $k$ $b$, meaning this interval is a linear function $y=kx+b$ (it is guaranteed that $k\ne 0$).
• $2$ $a$ $b$ $c$, meaning this interval is a quadratic function $y=ax^2+bx+c$ (it is guaranteed that $a\ne 0$).

From line $n+2$ to line $n+q+1$, each line contains two integers $op,k$ separated by spaces:

• If $op=1$, output the value of $y$ when $x=k$ (it is guaranteed that $k\in (0,r_n]$).
• If $op=2$, output how many intersection points the line $y=k$ has with the whole piecewise function within the range $(0,r_n]$.

Output Format

There are $q$ lines in total. Each line contains one integer, the answer to the corresponding query.

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

Hint

Sample Explanation #1

The three segments are $y=x+2$, $y=x^2-2x+1$, and $y=x$.

For $x=4$, substituting into the second segment gives the result $9$.

The line $y=5$ intersects the first and second segments, and each has exactly one intersection point, so the result is $2$.

Obviously, the line corresponding to the third query does not intersect the function.

Although the line in the fourth query intersects the first segment at $x=0$, $0$ is not in that segment's interval, so it is discarded.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n,q\le 2\times 10^5$, $0\le l_i,r_i\le 10^9$, and $\forall i\in [1,n],r_i>l_i$.

All function coefficients are within the storage range of 64-bit signed integers, and the computation results, as well as the maximum and minimum values of any term in each function expression, will not exceed the storage range of 64-bit signed integers. All query parameters are within the range of 32-bit signed integers.

(i.e. $-4\times 10^{18}\le k,a,b,c\le 4\times 10^{18}$, $-10^9\le x\le 10^9$)

Hint

When using floating-point numbers, it is recommended to use long double to avoid precision issues.

upd: A set of hack testdata has been added. If you do not pass it, it will show as "Unaccepted 100pts".

Translated by ChatGPT 5