P8929 "TERRA-OI R1" Don't Get Cocky, Kid.

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......

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.

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]$.

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

#### 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.** | Subtask | Score | $n,q\le$ | limit | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $100$ | None | | $2$ | $15$ | $10^3$ | $r_n\le 5\times 10^3$ | | $3$ | $20$ | $2\times 10^5$ | No query of type $2$ | | $4$ | $25$ | $2\times 10^5$ | No quadratic function | | $5$ | $30$ | $2\times 10^5$ | None | 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