← 返回题目列表

Codeforces · 453/E

E. 小马驹和提雷克勋爵

中文机器翻译题面 查看原题

提雷克勋爵是半人马,也是剧集“我的小马驹:友谊就是魔法”第四季最后一集中的主要反派。在“暮光之国”(第 1 部分)中,提雷克逃离了塔耳塔洛斯,并从小马身上汲取魔法以变得更加强大。

提雷克的核心技能称为吸收法力。它会从魔法生物身上获取所有法力并将其交给施法者。

现在为了简化问题,假设您有 n 匹小马(编号从 1 到 n)。每匹小马都有三个属性:

- si :小马在时间 0 时拥有的法力值;
- mi :小马可以拥有的最大法力值;
- ri :每单位时间的法力再生。

提雷克勋爵会执行 m 条指令,每条指令都可以用三个整数来描述:ti、li、ri。该指令意味着在时间 ti 时,提雷克将对编号从 li 到 ri(包括边界)的小马使用吸收法力。我们将按顺序向您提供所有 m 个指令,计算每个指令提雷克吸收了多少法力。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 小马的数量。接下来的 n 行每一行包含三个整数 si、mi、ri (0 ≤ si ≤ mi ≤ 105; 0 ≤ ri ≤ 105),描述一匹小马。

下一行包含一个整数 m (1 ≤ m ≤ 105) — 指令数。接下来的 m 行中的每一行包含三个整数 ti、li、ri (0 ≤ ti ≤ 109; 1 ≤ li ≤ ri ≤ n),描述了 Lord Tirek 的一条指令。这些指令按照 ti 严格递增的顺序给出(所有 ti 都是不同的)。

输出

对于每条指令,输出一行,其中包含一个整数,即该指令吸收的总法力。

示例

输入 #1

5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5

输出 #1

25
58

注意

每匹小马一开始的法力都是零。对于第一个指令,每匹小马都有 5 点法力,因此您总共获得 25 点法力,并且在第一个指令之后每匹马都有 0 点法力。

对于第二条指令,小马 3 有 14 点法力,其他小马的法力等于他们的 mi。