← 返回题目列表

Codeforces · 837/G

G. 各段的功能

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

您有一个由 n 个函数组成的数组 f。函数 fi(x) (1 ≤ i ≤ n) 的特征在于参数:x1、x2、y1、a、b、y2 并取值:

- y1,如果 x ≤ x1。
- a·x + b,如果 x1 < x ≤ x2。
- y2,如果 x > x2。

有 m 个查询。每个查询由数字 l、r 和 x 确定。对于编号为 i (1 ≤ i ≤ m) 的查询,您需要计算所有 fj(xi) 的总和,其中 l ≤ j ≤ r。 xi 的值计算如下:xi = (x + last) mod 109,其中last 是编号为 i - 1 的查询的答案。如果 i = 1,last 的值等于 0。

输入

第一行包含一个整数 n (1 ≤ n ≤ 75000)。

接下来的 n 行每行包含六个整数:x1, x2, y1, a, b, y2 (0 ≤ x1 < x2 ≤ 2·105, 0 ≤ y1, y2 ≤ 109, 0 ≤ a, b ≤ 104)。

下一行包含一个整数 m (1 ≤ m ≤ 500000)。

接下来的 m 行每行包含三个整数:l、r 和 x (1 ≤ l ≤ r ≤ n,0 ≤ x ≤ 109)。

示例

输入 #1

1
1 2 1 4 5 10
1
1 1 2

输出 #1

13

输入 #2

3
2 5 1 1 1 4
3 6 8 2 5 7
1 3 5 1 4 10
3
1 3 3
2 3 2
1 2 5

输出 #2

19
17
11