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⁹).

Functions On The Segments

Examples