P8797 [Lanqiao Cup 2022 National A] Triangle Sequence

Thanks to [Lotuses](https://www.luogu.com.cn/user/414231) for providing the testdata.

Given $n$ pairs of numbers $a_i, b_i$, each pair represents a triangle with $a_i$ rows and $a_i$ columns as shown in the figure:  When $b_i = 0$, the left side is lower; when $b_i = 1$, the right side is lower. Concatenate the triangles corresponding to each pair from left to right in the given order. Now there are $m$ queries $l_i, r_i, v_i$. For each query, find the minimum height $h_i$ such that, between columns $l_i$ and $r_i$, the number of $o$ whose height is within $h_i$ is at least $v_i$.

The first line contains two integers $n, m$, separated by a space. The next $n$ lines each contain two integers $a_i, b_i$, separated by a space. The next $m$ lines each contain three integers $l_i, r_i, v_i$, where adjacent integers are separated by a space.

Output one line containing a string representing the answer.

**Sample Explanation** The range corresponding to the first query is shown in the figure:  **Constraints** - For $30\%$ of the test cases, $1 \leq n, m, a_i \leq 500$. - For $50\%$ of the test cases, $1 \leq n, m, a_i \leq 5000$. - For all test cases, $1 \leq n, m \leq 2\times10^5$, $1 \leq a_i \leq 10^6$, $0 \leq b_i \leq 1$, $1 \leq l_i \leq r_i \leq \sum a_i$, $1 \leq v_i \leq 10^{18}$. Lanqiao Cup 2022 National Contest A Group, Problem I. Translated by ChatGPT 5