题目背景

公告：注意存在 $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_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$，如果可以，他会领取一份礼品。

请你帮他快速求出每次行走结束后他的愉悦值。

输入格式

第一行，两个整数 $n, m$；

接下来 $n$ 行，其中第 $i$ 行有三个整数 $l_i, r_i, v_i$；

接下来 $m$ 行，每行三个整数 $l, r, x$，表示一个询问。

输出格式

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

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

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