Functions On The Segments

5000ms

1048576K

Description:

You have an array f of n functions.The function f_i(x) (1 ≤ i ≤ n) is characterized by parameters: x₁, x₂, y₁, a, b, y₂ and take values:

y₁, if x ≤ x₁.
a·x + b, if x₁ < x ≤ x₂.
y₂, if x > x₂.

There are m queries. Each query is determined by numbers l, r and x. For a query with number i (1 ≤ i ≤ m), you need to calculate the sum of all f_j(x_i) where l ≤ j ≤ r. The value of x_i is calculated as follows: x_i = (x + last) mod 10⁹, where last is the answer to the query with number i - 1. The value of last equals 0 if i = 1.

Input:

First line contains one integer number n (1 ≤ n ≤ 75000).

Each of the next n lines contains six integer numbers: x₁, x₂, y₁, a, b, y₂ (0 ≤ x₁ < x₂ ≤ 2·10⁵, 0 ≤ y₁, y₂ ≤ 10⁹, 0 ≤ a, b ≤ 10⁴).

Next line contains one integer number m (1 ≤ m ≤ 500000).

Each of the next m lines contains three integer numbers: l, r and x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 10⁹).

Sample Input:

1
1 2 1 4 5 10
1
1 1 2

Sample Output:

Sample Input:

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

Sample Output:

19
17
11

Informação

Provedor Codeforces

Código CF837G