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