#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 100, md = 1e9;
struct inf {
  long long x[2], y[2], a, b;
} a[nmax];
struct st {
  long long s[4], laz[4];
  st *l, *r;
  st() {
    for (int i = (int)0; i <= (int)3; i++) s[i] = laz[i] = 0;
    l = r = NULL;
  }
} * ver[nmax];
bool inside(int a, int b, int c) { return (a >= b && a <= c); }
bool intersect(int a, int b, int c, int d) {
  return (inside(a, c, d) || inside(b, c, d) || inside(c, a, b) ||
          inside(d, a, b));
}
void build(st *node, int l, int r) {
  if (l == r) return;
  node->l = new st;
  node->r = new st;
  build(node->l, l, ((l + r) >> 1) + 0);
  build(node->r, ((l + r) >> 1) + 1, r);
}
void upd(st *node1, st *node2, int l, int r, int u, int v, long long v1,
         long long v2, long long v3, long long v4) {
  if (l > v || r < u || u > v || u > (int)2e5) return;
  if (l >= u && r <= v) {
    node2->l = node1->l, node2->r = node1->r;
    node2->laz[0] = node1->laz[0] + v1;
    node2->laz[1] = node1->laz[1] + v2;
    node2->laz[2] = node1->laz[2] + v3;
    node2->laz[3] = node1->laz[3] + v4;
    node2->s[0] = node1->s[0] + v1 * (r - l + 1);
    node2->s[1] = node1->s[1] + v2 * (r - l + 1);
    node2->s[2] = node1->s[2] + v3 * (r - l + 1);
    node2->s[3] = node1->s[3] + v4 * (r - l + 1);
    return;
  }
  intersect(l, ((l + r) >> 1) + 0, u, v) ? node2->l = new st
                                         : node2->l = node1->l;
  intersect(((l + r) >> 1) + 1, r, u, v) ? node2->r = new st
                                         : node2->r = node1->r;
  upd(node1->l, node2->l, l, ((l + r) >> 1) + 0, u, v, v1, v2, v3, v4);
  upd(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v, v1, v2, v3, v4);
  for (int i = (int)0; i <= (int)3; i++)
    node2->laz[i] = node1->laz[i],
    node2->s[i] = (node2->l)->s[i] + (node2->r)->s[i];
}
long long get(st *node1, st *node2, int l, int r, int x) {
  if (l > x || r < x) return 0;
  if (l == r) {
    long long tmp = node2->s[0] - node1->s[0] + node2->s[1] - node1->s[1] +
                    node2->s[3] - node1->s[3];
    return tmp + (node2->s[2] - node1->s[2]) * 1ll * x;
  }
  long long tmp = node2->laz[0] - node1->laz[0] + node2->laz[1] -
                  node1->laz[1] + node2->laz[3] - node1->laz[3];
  tmp += (node2->laz[2] - node1->laz[2]) * x;
  return get(node1->l, node2->l, l, ((l + r) >> 1), x) +
         get(node1->r, node2->r, ((l + r) >> 1) + 1, r, x) + tmp;
}
long long cheat[nmax];
int main() {
  ios_base::sync_with_stdio(false);
  long long m = 2e5, lst = 0, l, r, x, n, q;
  cin >> n;
  for (int i = (int)1; i <= (int)n; i++) {
    cin >> a[i].x[0] >> a[i].x[1] >> a[i].y[0] >> a[i].a >> a[i].b >> a[i].y[1];
    cheat[i] = cheat[i - 1] + a[i].y[1];
  }
  build(ver[0] = new st, 0, m);
  for (int i = (int)1; i <= (int)n; i++) {
    st *tmp[3] = {new st, new st, new st};
    upd(ver[i - 1], tmp[0], 0, m, 0, a[i].x[0], a[i].y[0], 0, 0, 0);
    if (a[i].x[1] + 1 <= m)
      upd(tmp[0], tmp[1], 0, m, a[i].x[1] + 1, m, 0, a[i].y[1], 0, 0);
    else
      tmp[1] = tmp[0];
    upd(tmp[1], tmp[2], 0, m, a[i].x[0] + 1, a[i].x[1], 0, 0, a[i].a, a[i].b);
    ver[i] = tmp[2];
  }
  cin >> q;
  while (q--) {
    cin >> l >> r >> x;
    (x += lst) %= md;
    (x > m) ? lst = cheat[r] - cheat[l - 1]
            : lst = get(ver[l - 1], ver[r], 0, m, x);
    cout << lst << "\n";
  }
}

### Prompt

Construct a CPP code solution to the problem outlined:

You have an array f of n functions.The function fi(x) (1 ≤ i ≤ n) is characterized by parameters: x1, x2, y1, a, b, y2 and take values: 

  * y1, if x ≤ x1. 
  * a·x + b, if x1 < x ≤ x2. 
  * y2, if x > x2. 



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 fj(xi) where l ≤ j ≤ r. The value of xi is calculated as follows: xi = (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: x1, x2, y1, a, b, y2 (0 ≤ x1 < x2 ≤ 2·105, 0 ≤ y1, y2 ≤ 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).

Examples

Input

1
1 2 1 4 5 10
1
1 1 2


Output

13


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


Output

19
17
11

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 100, md = 1e9;
struct inf {
  long long x[2], y[2], a, b;
} a[nmax];
struct st {
  long long s[4], laz[4];
  st *l, *r;
  st() {
    for (int i = (int)0; i <= (int)3; i++) s[i] = laz[i] = 0;
    l = r = NULL;
  }
} * ver[nmax];
bool inside(int a, int b, int c) { return (a >= b && a <= c); }
bool intersect(int a, int b, int c, int d) {
  return (inside(a, c, d) || inside(b, c, d) || inside(c, a, b) ||
          inside(d, a, b));
}
void build(st *node, int l, int r) {
  if (l == r) return;
  node->l = new st;
  node->r = new st;
  build(node->l, l, ((l + r) >> 1) + 0);
  build(node->r, ((l + r) >> 1) + 1, r);
}
void upd(st *node1, st *node2, int l, int r, int u, int v, long long v1,
         long long v2, long long v3, long long v4) {
  if (l > v || r < u || u > v || u > (int)2e5) return;
  if (l >= u && r <= v) {
    node2->l = node1->l, node2->r = node1->r;
    node2->laz[0] = node1->laz[0] + v1;
    node2->laz[1] = node1->laz[1] + v2;
    node2->laz[2] = node1->laz[2] + v3;
    node2->laz[3] = node1->laz[3] + v4;
    node2->s[0] = node1->s[0] + v1 * (r - l + 1);
    node2->s[1] = node1->s[1] + v2 * (r - l + 1);
    node2->s[2] = node1->s[2] + v3 * (r - l + 1);
    node2->s[3] = node1->s[3] + v4 * (r - l + 1);
    return;
  }
  intersect(l, ((l + r) >> 1) + 0, u, v) ? node2->l = new st
                                         : node2->l = node1->l;
  intersect(((l + r) >> 1) + 1, r, u, v) ? node2->r = new st
                                         : node2->r = node1->r;
  upd(node1->l, node2->l, l, ((l + r) >> 1) + 0, u, v, v1, v2, v3, v4);
  upd(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v, v1, v2, v3, v4);
  for (int i = (int)0; i <= (int)3; i++)
    node2->laz[i] = node1->laz[i],
    node2->s[i] = (node2->l)->s[i] + (node2->r)->s[i];
}
long long get(st *node1, st *node2, int l, int r, int x) {
  if (l > x || r < x) return 0;
  if (l == r) {
    long long tmp = node2->s[0] - node1->s[0] + node2->s[1] - node1->s[1] +
                    node2->s[3] - node1->s[3];
    return tmp + (node2->s[2] - node1->s[2]) * 1ll * x;
  }
  long long tmp = node2->laz[0] - node1->laz[0] + node2->laz[1] -
                  node1->laz[1] + node2->laz[3] - node1->laz[3];
  tmp += (node2->laz[2] - node1->laz[2]) * x;
  return get(node1->l, node2->l, l, ((l + r) >> 1), x) +
         get(node1->r, node2->r, ((l + r) >> 1) + 1, r, x) + tmp;
}
long long cheat[nmax];
int main() {
  ios_base::sync_with_stdio(false);
  long long m = 2e5, lst = 0, l, r, x, n, q;
  cin >> n;
  for (int i = (int)1; i <= (int)n; i++) {
    cin >> a[i].x[0] >> a[i].x[1] >> a[i].y[0] >> a[i].a >> a[i].b >> a[i].y[1];
    cheat[i] = cheat[i - 1] + a[i].y[1];
  }
  build(ver[0] = new st, 0, m);
  for (int i = (int)1; i <= (int)n; i++) {
    st *tmp[3] = {new st, new st, new st};
    upd(ver[i - 1], tmp[0], 0, m, 0, a[i].x[0], a[i].y[0], 0, 0, 0);
    if (a[i].x[1] + 1 <= m)
      upd(tmp[0], tmp[1], 0, m, a[i].x[1] + 1, m, 0, a[i].y[1], 0, 0);
    else
      tmp[1] = tmp[0];
    upd(tmp[1], tmp[2], 0, m, a[i].x[0] + 1, a[i].x[1], 0, 0, a[i].a, a[i].b);
    ver[i] = tmp[2];
  }
  cin >> q;
  while (q--) {
    cin >> l >> r >> x;
    (x += lst) %= md;
    (x > m) ? lst = cheat[r] - cheat[l - 1]
            : lst = get(ver[l - 1], ver[r], 0, m, x);
    cout << lst << "\n";
  }
}

```