您有一个由 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