「SFCOI-3」进行一个走的行

小 L 来到了一处景点，他想要在这里的主干道上行走。 主干道上有若干关键点，他可以将其抽象为一个长为 $n$ 的序列 $a$，每个 $a_i$ 都是一个三元组，可以表示为 $(l_i, r_i, v_i)$，其具体含义形如： - 若 $r_i = -1$，表示一个需要买票进入的景点，票价为 $l_i$ 代币，游览完成后他会得到 $v_i$ 的愉悦值。 - 若 $r_i \neq -1$，表示一个礼品派发点，若他持有的代币面值之和 $x$ 满足 $l_i \leq x \leq r_i$，他可以领取一份礼品，并会得到 $v_i$ 的愉悦值。 他打算在这条主干道上行走 $m$ 次，每次他给出了行走起点 $l$ 和终点 $r$，一开始他持有的代币面值之和为 $x$，初始愉悦值为 $0$。 他将从 $l$ 开始向右依次经过 $i \in [l, r]$，他会做如下操作： - 若 $r_i = -1$，如果他持有的代币在支付完当前景点门票费用后还有剩余，他会游览这个景点。 - 若 $r_i \neq -1$，如果可以，他会领取一份礼品。 请你帮他快速求出每次行走结束后他的愉悦值。 ## Input 第一行，两个整数 $n, m$； 接下来 $n$ 行，其中第 $i$ 行有三个整数 $l_i, r_i, v_i$； 接下来 $m$ 行，每行三个整数 $l, r, x$，表示一个询问。 ## Output $m$ 行，每行一个整数，表示行走结束后他的愉悦值。 [samples] ## Background **公告：注意存在 $l_i > r_i$ 的情况，此时操作无效。** ------------ 小 L 热衷于行走。 ## Note **本题开启捆绑测试。** - Subtask 1（10 pts）：$1 \leq n, m \leq 5 \times 10^3$。 - Subtask 2（10 pts）：$r_i \neq -1$。 - Subtask 3（20 pts）：$r_i = -1$。 - Subtask 4（10 pts）：$1 \leq n, m \leq 7.5 \times 10^4$，性质 A。 - Subtask 5（20 pts）：$1 \leq n, m \leq 7.5 \times 10^4$。 - Subtask 6（10 pts）：数据在范围内随机生成，性质 B。 - Subtask 7（20 pts）：无特殊限制。 性质 A：$1 \leq l_i \leq 7.5 \times 10^4$，$r_i = -1$ 或 $1 \leq r_i \leq 7.5 \times 10^4$，$1 \leq x \leq 7.5 \times 10^4$。 性质 B：$r_i = -1$ 时 $1 \leq l_i \leq 2 \times 10^5$。 对于 $100\%$ 的数据： - $1 \leq n, m \leq 2 \times 10^5$。 - $1 \leq l_i \leq 10^9$，$r_i = -1$ 或 $1 \leq r_i \leq 10^9$。 - $1 \leq v_i \leq 10^9$。 - $1 \leq l \leq r \leq n$，$1 \leq x \leq 10^9$。