#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5, mod = 1e9, nmax = 2e5 + 100;
struct seg1 {
  long long s;
  seg1 *l, *r;
  seg1() {
    s = 0;
    l = NULL;
    r = NULL;
  }
} * ver1[nmax];
struct seg2 {
  long long s;
  seg2 *l, *r;
  seg2() {
    s = 0;
    l = NULL;
    r = NULL;
  }
} * ver2[nmax];
struct seg3 {
  long long A, B, laz[2];
  seg3 *l, *r;
  seg3() {
    A = B = laz[0] = laz[1] = 0;
    l = NULL;
    r = NULL;
  }
} * ver3[nmax];
struct inf {
  long long x[2], y[2], a, b;
} a[nmax];
void build_1(seg1 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg1;
  node->r = new seg1;
  build_1(node->l, l, ((l + r) >> 1) + 0);
  build_1(node->r, ((l + r) >> 1) + 1, r);
}
void build_2(seg2 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg2;
  node->r = new seg2;
  build_2(node->l, l, ((l + r) >> 1) + 0);
  build_2(node->r, ((l + r) >> 1) + 1, r);
}
void build_3(seg3 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg3;
  node->r = new seg3;
  build_3(node->l, l, ((l + r) >> 1) + 0);
  build_3(node->r, ((l + r) >> 1) + 1, r);
}
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 upd1(seg1 *node1, seg1 *node2, int l, int r, int p, long long v) {
  if (l == r) {
    node2->s = node1->s + v;
    return;
  }
  if (inside(p, l, ((l + r) >> 1)))
    node2->r = node1->r,
    upd1(node1->l, node2->l = new seg1, l, ((l + r) >> 1) + 0, p, v);
  else
    node2->l = node1->l,
    upd1(node1->r, node2->r = new seg1, ((l + r) >> 1) + 1, r, p, v);
  node2->s = (node2->l)->s + (node2->r)->s;
}
void upd2(seg2 *node1, seg2 *node2, int l, int r, int p, long long v) {
  if (l == r) {
    node2->s = node1->s + v;
    return;
  }
  if (inside(p, l, ((l + r) >> 1)))
    node2->r = node1->r,
    upd2(node1->l, node2->l = new seg2, l, ((l + r) >> 1) + 0, p, v);
  else
    node2->l = node1->l,
    upd2(node1->r, node2->r = new seg2, ((l + r) >> 1) + 1, r, p, v);
  node2->s = (node2->l)->s + (node2->r)->s;
}
void upd3(seg3 *node1, seg3 *node2, int l, int r, int u, int v, long long A,
          long long B) {
  if (l > v || r < u) {
    return;
  }
  if (l >= u && r <= v) {
    node2->laz[0] = node1->laz[0] + A;
    node2->laz[1] = node1->laz[1] + B;
    node2->A = node1->A + A * (r - l + 1);
    node2->B = node1->B + B * (r - l + 1);
    if (l != r) node2->l = node1->l, node2->r = node1->r;
    return;
  }
  (intersect(l, ((l + r) >> 1) + 0, u, v)) ? node2->l = new seg3
                                           : node2->l = node1->l;
  (intersect(((l + r) >> 1) + 1, r, u, v)) ? node2->r = new seg3
                                           : node2->r = node1->r;
  upd3(node1->l, node2->l, l, ((l + r) >> 1) + 0, u, v, A, B);
  upd3(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v, A, B);
  node2->A = (node2->l)->A + (node2->r)->A;
  node2->B = (node2->l)->B + (node2->r)->B;
  for (int i = (int)0; i <= (int)1; i++) node2->laz[i] += node1->laz[i];
}
long long n;
long long sum[nmax];
void in() {
  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];
    sum[i] = sum[i - 1] + a[i].y[1];
  }
  build_1(ver1[0] = new seg1, 0, mx);
  build_2(ver2[0] = new seg2, 0, mx);
  build_3(ver3[0] = new seg3, 0, mx);
  for (int i = (int)1; i <= (int)n; i++) {
    upd1(ver1[i - 1], ver1[i] = new seg1, 0, mx, a[i].x[0], a[i].y[0]);
    upd2(ver2[i - 1], ver2[i] = new seg2, 0, mx, a[i].x[1], a[i].y[1]);
    upd3(ver3[i - 1], ver3[i] = new seg3, 0, mx, a[i].x[0] + 1, a[i].x[1],
         a[i].a, a[i].b);
  }
}
long long get1(seg1 *node1, seg1 *node2, int l, int r, int u, int v) {
  if (l > v || r < u) return 0;
  if (l >= u && r <= v) return node2->s - node1->s;
  return get1(node1->l, node2->l, l, ((l + r) >> 1), u, v) +
         get1(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v);
}
long long get2(seg2 *node1, seg2 *node2, int l, int r, int u, int v) {
  if (l > v || r < u) return 0;
  if (l >= u && r <= v) return node2->s - node1->s;
  return get2(node1->l, node2->l, l, ((l + r) >> 1), u, v) +
         get2(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v);
}
void collect(seg3 *node1, seg3 *node2, int l, int r, int p, long long &A,
             long long &B) {
  if (l == r) {
    A += node2->A - node1->A;
    B += node2->B - node1->B;
    return;
  }
  A += node2->laz[0] - node1->laz[0];
  B += node2->laz[1] - node1->laz[1];
  (p >= l && p <= ((l + r) >> 1))
      ? collect(node1->l, node2->l, l, ((l + r) >> 1), p, A, B)
      : collect(node1->r, node2->r, ((l + r) >> 1) + 1, r, p, A, B);
}
long long querry(long long l, long long r, long long x) {
  if (x > (int)2e5) return sum[r] - sum[l - 1];
  long long rs = get1(ver1[l - 1], ver1[r], 0, mx, x, mx) +
                 get2(ver2[l - 1], ver2[r], 0, mx, 0, x - 1);
  long long A = 0, B = 0;
  collect(ver3[l - 1], ver3[r], 0, mx, x, A, B);
  return rs + x * A + B;
}
void so() {
  long long m, l, r, x;
  long long last = 0;
  cin >> m;
  for (int i = (int)1; i <= (int)m; i++) {
    cin >> l >> r >> x;
    long long tmp = querry(l, r, (x + last) % mod);
    cout << tmp << "\n";
    last = tmp;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  in();
  so();
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 mx = 2e5, mod = 1e9, nmax = 2e5 + 100;
struct seg1 {
  long long s;
  seg1 *l, *r;
  seg1() {
    s = 0;
    l = NULL;
    r = NULL;
  }
} * ver1[nmax];
struct seg2 {
  long long s;
  seg2 *l, *r;
  seg2() {
    s = 0;
    l = NULL;
    r = NULL;
  }
} * ver2[nmax];
struct seg3 {
  long long A, B, laz[2];
  seg3 *l, *r;
  seg3() {
    A = B = laz[0] = laz[1] = 0;
    l = NULL;
    r = NULL;
  }
} * ver3[nmax];
struct inf {
  long long x[2], y[2], a, b;
} a[nmax];
void build_1(seg1 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg1;
  node->r = new seg1;
  build_1(node->l, l, ((l + r) >> 1) + 0);
  build_1(node->r, ((l + r) >> 1) + 1, r);
}
void build_2(seg2 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg2;
  node->r = new seg2;
  build_2(node->l, l, ((l + r) >> 1) + 0);
  build_2(node->r, ((l + r) >> 1) + 1, r);
}
void build_3(seg3 *node, int l, int r) {
  if (l == r) return;
  node->l = new seg3;
  node->r = new seg3;
  build_3(node->l, l, ((l + r) >> 1) + 0);
  build_3(node->r, ((l + r) >> 1) + 1, r);
}
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 upd1(seg1 *node1, seg1 *node2, int l, int r, int p, long long v) {
  if (l == r) {
    node2->s = node1->s + v;
    return;
  }
  if (inside(p, l, ((l + r) >> 1)))
    node2->r = node1->r,
    upd1(node1->l, node2->l = new seg1, l, ((l + r) >> 1) + 0, p, v);
  else
    node2->l = node1->l,
    upd1(node1->r, node2->r = new seg1, ((l + r) >> 1) + 1, r, p, v);
  node2->s = (node2->l)->s + (node2->r)->s;
}
void upd2(seg2 *node1, seg2 *node2, int l, int r, int p, long long v) {
  if (l == r) {
    node2->s = node1->s + v;
    return;
  }
  if (inside(p, l, ((l + r) >> 1)))
    node2->r = node1->r,
    upd2(node1->l, node2->l = new seg2, l, ((l + r) >> 1) + 0, p, v);
  else
    node2->l = node1->l,
    upd2(node1->r, node2->r = new seg2, ((l + r) >> 1) + 1, r, p, v);
  node2->s = (node2->l)->s + (node2->r)->s;
}
void upd3(seg3 *node1, seg3 *node2, int l, int r, int u, int v, long long A,
          long long B) {
  if (l > v || r < u) {
    return;
  }
  if (l >= u && r <= v) {
    node2->laz[0] = node1->laz[0] + A;
    node2->laz[1] = node1->laz[1] + B;
    node2->A = node1->A + A * (r - l + 1);
    node2->B = node1->B + B * (r - l + 1);
    if (l != r) node2->l = node1->l, node2->r = node1->r;
    return;
  }
  (intersect(l, ((l + r) >> 1) + 0, u, v)) ? node2->l = new seg3
                                           : node2->l = node1->l;
  (intersect(((l + r) >> 1) + 1, r, u, v)) ? node2->r = new seg3
                                           : node2->r = node1->r;
  upd3(node1->l, node2->l, l, ((l + r) >> 1) + 0, u, v, A, B);
  upd3(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v, A, B);
  node2->A = (node2->l)->A + (node2->r)->A;
  node2->B = (node2->l)->B + (node2->r)->B;
  for (int i = (int)0; i <= (int)1; i++) node2->laz[i] += node1->laz[i];
}
long long n;
long long sum[nmax];
void in() {
  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];
    sum[i] = sum[i - 1] + a[i].y[1];
  }
  build_1(ver1[0] = new seg1, 0, mx);
  build_2(ver2[0] = new seg2, 0, mx);
  build_3(ver3[0] = new seg3, 0, mx);
  for (int i = (int)1; i <= (int)n; i++) {
    upd1(ver1[i - 1], ver1[i] = new seg1, 0, mx, a[i].x[0], a[i].y[0]);
    upd2(ver2[i - 1], ver2[i] = new seg2, 0, mx, a[i].x[1], a[i].y[1]);
    upd3(ver3[i - 1], ver3[i] = new seg3, 0, mx, a[i].x[0] + 1, a[i].x[1],
         a[i].a, a[i].b);
  }
}
long long get1(seg1 *node1, seg1 *node2, int l, int r, int u, int v) {
  if (l > v || r < u) return 0;
  if (l >= u && r <= v) return node2->s - node1->s;
  return get1(node1->l, node2->l, l, ((l + r) >> 1), u, v) +
         get1(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v);
}
long long get2(seg2 *node1, seg2 *node2, int l, int r, int u, int v) {
  if (l > v || r < u) return 0;
  if (l >= u && r <= v) return node2->s - node1->s;
  return get2(node1->l, node2->l, l, ((l + r) >> 1), u, v) +
         get2(node1->r, node2->r, ((l + r) >> 1) + 1, r, u, v);
}
void collect(seg3 *node1, seg3 *node2, int l, int r, int p, long long &A,
             long long &B) {
  if (l == r) {
    A += node2->A - node1->A;
    B += node2->B - node1->B;
    return;
  }
  A += node2->laz[0] - node1->laz[0];
  B += node2->laz[1] - node1->laz[1];
  (p >= l && p <= ((l + r) >> 1))
      ? collect(node1->l, node2->l, l, ((l + r) >> 1), p, A, B)
      : collect(node1->r, node2->r, ((l + r) >> 1) + 1, r, p, A, B);
}
long long querry(long long l, long long r, long long x) {
  if (x > (int)2e5) return sum[r] - sum[l - 1];
  long long rs = get1(ver1[l - 1], ver1[r], 0, mx, x, mx) +
                 get2(ver2[l - 1], ver2[r], 0, mx, 0, x - 1);
  long long A = 0, B = 0;
  collect(ver3[l - 1], ver3[r], 0, mx, x, A, B);
  return rs + x * A + B;
}
void so() {
  long long m, l, r, x;
  long long last = 0;
  cin >> m;
  for (int i = (int)1; i <= (int)m; i++) {
    cin >> l >> r >> x;
    long long tmp = querry(l, r, (x + last) % mod);
    cout << tmp << "\n";
    last = tmp;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  in();
  so();
}

```