题目描述

观者拥有一个正整数能量值。在战斗过程中，观者会呈现出三种不同的姿态：

1. 无姿态：没有任何效果。
2. 愤怒姿态：在这个姿态中，观者能造成双倍攻击伤害。
3. 平静姿态：离开这一姿态时，获得两点能量。

观者的卡组有 $n$ 张卡牌。第 $i$ 张卡牌有以下三个参数：

• $x_i(0\le x_i\le 3)$ ，表示打出这张牌所需的能量。
• $y_i(0\le y_i\le 1000)$ ，表示这张牌的基础伤害。
• $z_i$ ，表示使用后观者将进入的新姿态。

在尝试打出第 $i$ 张牌之后：

• 如果观者当前的能量值低于 $x_i$ ：什么也不会发生，该卡牌打出失败。
• 否则：成功打出了这张卡，触发了以下效果：
  • 观者必须立刻支付 $x_i$ 点能量。
  • 观者对敌人造成 $y_i$ 点攻击伤害。如果观者处于愤怒姿态，则将会造成两倍的伤害。
  • 观者的姿态切换为 $z_i$ 。此时如果观者原先处于平静姿态且 $z_i$ 不是平静，则观者获得两点能量。

现在，观者将会进行 $m$ 次战斗，第 $i$ 次战斗将会给出 $l_i, r_i,s_i,k_i$ ，表示观者初始拥有 $s_i$ 点能量，初始姿态为 $k_i$ ，在战斗中按照顺序依次尝试打出了第 $l_i, l_i + 1, \dots, r_i$ 张牌。观者希望知道每次战斗能造成的伤害总和。

输入格式

输入的第一行包含一个非负整数 $c$ ，表示子任务编号。$c = 0$ 表示该测试点为样例。

输入的第二行包含两个非负整数 $n, m$ ，分别卡牌数量和询问个数。

接下来 $n$ 行，每行三个非负整数 $x_i, y_i, z_i$ ，分别表示第 $i$ 张卡牌的参数。为了方便读入，用 $0$ 表示无姿态，$1$ 表示愤怒姿态，$2$ 表示平静姿态，下同。

接下来 $m$ 行，每行四个非负整数 $l_i, r_i, s_i, k_i$ ，含义见上。

输出格式

输出 $m$ 行，第 $i$ 行表示第 $i$ 次战斗能造成的伤害总和。

样例 1 输入

0
10 5
1 9 1
1 0 2
1 9 1
1 0 2
1 9 1
1 8 2
2 40 1
1 9 1
2 40 1
1 16 1
4 8 2 2
5 8 1 1
1 10 2 2
1 10 3 0
3 10 1 2

样例 1 输出

34
18
133
132
123

样例 1 解释

对于第一次战斗：

• 初始能量为 $2$ ，姿态为平静。
• 成功打出了第 $4$ 张牌，姿态没有变化，能量值为 $2-1=1$ ，造成了 $0$ 点伤害。
• 成功打出了第 $5$ 张牌，造成了 $9$ 点伤害，姿态从平静变为愤怒，能量值为 $1-1+2=2$ 。
• 成功打出了第 $6$ 张牌，造成了 $8\times 2=16$ 点伤害，姿态从愤怒变为平静，能量值为 $2-1=1$ 。
• 第 $7$ 张牌打出失败。
• 成功打出了第 $8$ 张牌，造成了 $9$ 点伤害，姿态从平静变为愤怒，能量值为 $1-1+2=2$ 。
• 总伤害为 $9+16+9=34$ 。

数据范围

本题采用捆绑测试。

$1\le n, m\le 2\times 10^5$，$0\le x_i\le 3$ ，$0\le y_i\le 1000$，$0\le z_i,k_i\le 2$，$0\le s_i\le 3n$，$1\le l_i\le r_i\le n$ 。

特殊性质 A：$nm\le 10^7$ 。

特殊性质 B：$s_i=3n$ 。

特殊性质 C：$s_i\le 3$ 。

特殊性质 D：$r_i=n$ 。