You have an array _f_ of _n_ functions.The function _f__i_(_x_) (1 ≤ _i_ ≤ _n_) is characterized by parameters: _x_1, _x_2, _y_1, _a_, _b_, _y_2 and take values:
* _y_1, if _x_ ≤ _x_1.
* _a_·_x_ + _b_, if _x_1 < _x_ ≤ _x_2.
* _y_2, if _x_ > _x_2.
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 109, 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_1, _x_2, _y_1, _a_, _b_, _y_2 (0 ≤ _x_1 < _x_2 ≤ 2·105, 0 ≤ _y_1, _y_2 ≤ 109, 0 ≤ _a_, _b_ ≤ 104).
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_ ≤ 109).
[samples]
你有一个包含 $n$ 个函数的数组 $f$。函数 $f_i(x)$（$1 ≤ i ≤ n$）由参数 $x1, x2, y1, a, b, y2$ 描述，其取值如下：
共有 $m$ 个查询。每个查询由三个数 $l, r$ 和 $x$ 确定。对于第 $i$ 个查询（$1 ≤ i ≤ m$），你需要计算所有 $f_j(x_i)$ 的和，其中 $l ≤ j ≤ r$。值 $x_i$ 的计算方式如下：$x_i = (x + last) \mod 10^9$，其中 $last$ 是第 $i-1$ 个查询的答案。当 $i = 1$ 时，$last$ 的值为 $0$。
## Input
第一行包含一个整数 $n$（$1 ≤ n ≤ 75000$）。接下来的 $n$ 行每行包含六个整数：$x1, x2, y1, a, b, y2$（$0 ≤ x1 < x2 ≤ 2·10^5$，$0 ≤ y1, y2 ≤ 10^9$，$0 ≤ a, b ≤ 10^4$）。下一行包含一个整数 $m$（$1 ≤ m ≤ 500000$）。接下来的 $m$ 行每行包含三个整数：$l, r$ 和 $x$（$1 ≤ l ≤ r ≤ n$，$0 ≤ x ≤ 10^9$）。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of functions.
Let $ f_i : \mathbb{R} \to \mathbb{R} $, for $ i \in \{1, \dots, n\} $, be piecewise linear functions defined by parameters $ (x_{i,1}, x_{i,2}, y_{i,1}, a_i, b_i, y_{i,2}) $, where:
- $ 0 \le x_{i,1} < x_{i,2} \le 2 \cdot 10^5 $,
- $ 0 \le y_{i,1}, y_{i,2} \le 10^9 $,
- $ 0 \le a_i, b_i \le 10^4 $,
and for all $ x \in \mathbb{R} $:
$$
f_i(x) =
\begin{cases}
y_{i,1} & \text{if } x \le x_{i,1}, \\
a_i \cdot x + b_i & \text{if } x_{i,1} < x < x_{i,2}, \\
y_{i,2} & \text{if } x \ge x_{i,2}.
\end{cases}
$$
Let $ m \in \mathbb{Z}^+ $ be the number of queries.
Let $ Q = \{(l_i, r_i, x_i) \mid i \in \{1, \dots, m\}\} $ be the sequence of queries, where:
- $ 1 \le l_i \le r_i \le n $,
- $ 0 \le x_i \le 10^9 $.
Define the *last answer* sequence $ \text{last}_0 = 0 $, and for $ i \ge 1 $:
$$
x_i^{\text{actual}} = (x_i + \text{last}_{i-1}) \mod 10^9
$$
**Constraints**
1. $ 1 \le n \le 75000 $
2. $ 1 \le m \le 500000 $
3. All parameters satisfy the bounds above.
**Objective**
For each query $ i \in \{1, \dots, m\} $, compute:
$$
S_i = \sum_{j = l_i}^{r_i} f_j\left( x_i^{\text{actual}} \right)
$$
and set $ \text{last}_i = S_i $.
Output $ S_1, S_2, \dots, S_m $.