题目背景

感谢 Lotuses 提供的数据

题目描述

给定 $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$，相邻两个整数之间用一个空格分隔。

输出格式

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

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

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 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 题。