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

题目背景

**公告:注意存在 $l_i > r_i$ 的情况,此时操作无效。** ------------ 小 L 热衷于行走。

题目描述

小 L 来到了一处景点,他想要在这里的主干道上行走。 主干道上有若干关键点,他可以将其抽象为一个长为 $n$ 的序列 $a$,每个 $a_i$ 都是一个三元组,可以表示为 $(l_i, r_i, v_i)$,其具体含义形如: - 若 $r_i = -1$,表示一个需要买票进入的景点,票价为 $l_i$ 代币,游览完成后他会得到 $v_i$ 的愉悦值。 - 若 $r_i \neq -1$,表示一个礼品派发点,若他持有的代币面值之和 $x$ 满足 $l \leq x \leq r$,他可以领取一份礼品,并会得到 $v_i$ 的愉悦值。 他打算在这条主干道上行走 $m$ 次,每次他给出了行走起点 $l$ 和终点 $r$,一开始他持有的代币面值之和为 $x$,初始愉悦值为 $0$。 他将从 $l$ 开始向右依次经过 $i \in [l, r]$,他会做如下操作: - 若 $r_i = -1$,如果他持有的代币在支付完当前景点门票费用后还有剩余,他会游览这个景点。 - 若 $r_i \neq -1$,如果可以,他会领取一份礼品。 请你帮他快速求出每次行走结束后他的愉悦值。

输入输出格式

输入格式


第一行,两个整数 $n, m$; 接下来 $n$ 行,其中第 $i$ 行有三个整数 $l_i, r_i, v_i$; 接下来 $m$ 行,每行三个整数 $l, r, x$,表示一个询问。

输出格式


$m$ 行,每行一个整数,表示行走结束后他的愉悦值。

输入输出样例

输入样例 #1

4 10
1 1 4
5 -1 4
1 9 19
8 -1 10
1 1 11
2 2 4
3 3 5
4 4 14
1 2 1
2 3 9
3 4 1
1 3 9
2 4 8
1 4 10

输出样例 #1

0
0
19
10
4
23
19
23
23
23

说明

**本题开启捆绑测试。** - 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$。