三角序列 ### 问题描述 给定 $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}$ 以内的 $\circ$ 的数量大于等于 $v_{i}$ 。 ### 输入格式 输入的第一行包含两个整数 $n, m$, 用一个空格分隔。 接下来 $n$ 行, 每行包含两个整数 $a_{i}, b_{i}$, 用一个空格分隔。 接下来 $m$ 行, 每行包含三个整数 $l_{i}, r_{i}, v_{i}$, 相邻两个整数之间用一个空格分 隔。 ### 输出格式 输出 $m$ 行, 每行包含一个整数 $h_{i}$, 依次表示每次询问对应的答案。如果不 存在这样的 $h_{i}$, 请输出 $-1$ 。 ### 样例输入 ```text 6 6 3 0 4 0 2 1 3 1 5 0 1 1 3 9 12 3 9 13 3 4 4 14 16 7 9 15 12 1 18 42 ``` ### 样例输出 ```text 2 3 3 3 3 -1 ``` 样例说明 第一个询问对应的范围如图所示  ### 评测用例规模与约定 对于 $30 \\%$ 的评测用例, $1 \leq n, m, a_{i} \leq 500$; 对于 $50 \\%$ 的评测用例, $1 \leq n, m, a_{i} \leq 5000$; 对于所有评测用例, $1 \leq n, m \leq 200000,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}$ 。