P8797 [蓝桥杯 2022 国 A] 三角序列

感谢 [Lotuses](https://www.luogu.com.cn/user/414231) 提供的数据

给定 $n$ 组成对的数 $a_i, b_i$，每组数表示一个 $a_i$ 行 $a_i$ 列的如图所示的三角形：  其中 $b_i$ 为 $0$ 时左边较低，为 $1$ 时右边较低。 将每组数对应的三角按数的顺序从左到右拼接起来。 现给出 $m$ 组询问 $l_i, r_i, v_i$，对每组询问求最低高度 $h_i$ 使得 $l_i$ 到 $r_i$ 列之间的高度在 $h_i$ 以内的 $o$ 的数量大于等于 $v_i$。

输入的第一行包含两个整数 $n, m$，用一个空格分隔。 接下来 $n$ 行，每行包含两个整数 $a_i, b_i$，用一个空格分隔。 接下来 $m$ 行，每行包含三个整数 $l_i,r_i,v_i$，相邻两个整数之间用一个空格分隔。

输出一行包含一个字符串表示答案。

**【样例说明】** 第一个询问对应的范围如图所示  **【评测用例规模与约定】** - 对于 $30\%$ 的评测用例，$1 \leq n, m, a_i \leq 500$； - 对于 $50\%$ 的评测用例，$1 \leq n, m, a_i \leq 5000$； - 对于所有评测用例，$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}$。 蓝桥杯 2022 国赛 A 组 I 题。