{"raw_statement":[{"iden":"statement","content":"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:\n\n*   _y_1, if _x_ ≤ _x_1.\n*   _a_·_x_ + _b_, if _x_1 < _x_ ≤ _x_2.\n*   _y_2, if _x_ > _x_2.\n\nThere 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."},{"iden":"input","content":"First line contains one integer number _n_ (1 ≤ _n_ ≤ 75000).\n\nEach 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).\n\nNext line contains one integer number _m_ (1 ≤ _m_ ≤ 500000).\n\nEach of the next _m_ lines contains three integer numbers: _l_, _r_ and _x_ (1 ≤ _l_ ≤ _r_ ≤ _n_, 0 ≤ _x_ ≤ 109)."},{"iden":"examples","content":"Input\n\n1\n1 2 1 4 5 10\n1\n1 1 2\n\nOutput\n\n13\n\nInput\n\n3\n2 5 1 1 1 4\n3 6 8 2 5 7\n1 3 5 1 4 10\n3\n1 3 3\n2 3 2\n1 2 5\n\nOutput\n\n19\n17\n11"}],"translated_statement":[{"iden":"statement","content":"你有一个包含 $n$ 个函数的数组 $f$。函数 $f_i(x)$（$1 ≤ i ≤ n$）由参数 $x1, x2, y1, a, b, y2$ 描述，其取值如下：\n\n共有 $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$。"},{"iden":"input","content":"第一行包含一个整数 $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$）。"},{"iden":"examples","content":"输入1\n1 2 1 4 5 10\n1\n1 1 2\n输出13\n输入3\n2 5 1 1 1 4\n3 6 8 2 5 7\n1 3 5 1 4 10\n3\n1 3 3\n2 3 2\n1 2 5\n输出19\n17\n11"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of functions.  \nLet $ 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:  \n- $ 0 \\le x_{i,1} < x_{i,2} \\le 2 \\cdot 10^5 $,  \n- $ 0 \\le y_{i,1}, y_{i,2} \\le 10^9 $,  \n- $ 0 \\le a_i, b_i \\le 10^4 $,  \n\nand for all $ x \\in \\mathbb{R} $:  \n$$\nf_i(x) = \n\\begin{cases}\ny_{i,1} & \\text{if } x \\le x_{i,1}, \\\\\na_i \\cdot x + b_i & \\text{if } x_{i,1} < x < x_{i,2}, \\\\\ny_{i,2} & \\text{if } x \\ge x_{i,2}.\n\\end{cases}\n$$\n\nLet $ m \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ Q = \\{(l_i, r_i, x_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the sequence of queries, where:  \n- $ 1 \\le l_i \\le r_i \\le n $,  \n- $ 0 \\le x_i \\le 10^9 $.  \n\nDefine the *last answer* sequence $ \\text{last}_0 = 0 $, and for $ i \\ge 1 $:  \n$$\nx_i^{\\text{actual}} = (x_i + \\text{last}_{i-1}) \\mod 10^9\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 75000 $  \n2. $ 1 \\le m \\le 500000 $  \n3. All parameters satisfy the bounds above.  \n\n**Objective**  \nFor each query $ i \\in \\{1, \\dots, m\\} $, compute:  \n$$\nS_i = \\sum_{j = l_i}^{r_i} f_j\\left( x_i^{\\text{actual}} \\right)\n$$  \nand set $ \\text{last}_i = S_i $.  \n\nOutput $ S_1, S_2, \\dots, S_m $.","simple_statement":null,"has_page_source":false}