#include <bits/stdc++.h>
using namespace std;
int n, m, xA[200010], xB[200010], yA[200010], yB[200010], a[200010], b[200010],
    d[200010], Q;
int A[200010], B[200010];
long long ans = 0;
struct Num {
  int x, k, d;
} c[200010];
bool cmp(Num a, Num b) {
  if (a.x == b.x)
    return a.k < b.k;
  else
    return a.x < b.x;
}
struct Node {
  int ls, rs;
  long long s;
};
struct Tree {
  Node a[200010 * 30];
  int tot;
  void init() { tot = 0; }
  void pushup(int k) { a[k].s = a[a[k].ls].s + a[a[k].rs].s; }
  int Build(int l, int r, int q) {
    int k = ++tot;
    if (l == r) {
      a[k].ls = a[k].rs = 0;
      if (q == 0)
        a[k].s = yA[l];
      else
        a[k].s = 0;
      return k;
    }
    int mid = (l + r) >> 1;
    a[k].ls = Build(l, mid, q);
    a[k].rs = Build(mid + 1, r, q);
    pushup(k);
    return k;
  }
  int Update(int k, int l, int r, int pos, int x) {
    int nrt = ++tot;
    a[nrt] = a[k];
    if (l == r) {
      a[nrt].s += x;
      return nrt;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      a[nrt].ls = Update(a[k].ls, l, mid, pos, x);
    else
      a[nrt].rs = Update(a[k].rs, mid + 1, r, pos, x);
    pushup(nrt);
    return nrt;
  }
  long long Ask(int k, int l, int r, int L, int R) {
    if (l == L && r == R) return a[k].s;
    int mid = (l + r) >> 1;
    if (R <= mid)
      return Ask(a[k].ls, l, mid, L, R);
    else if (L > mid)
      return Ask(a[k].rs, mid + 1, r, L, R);
    else
      return Ask(a[k].ls, l, mid, L, mid) +
             Ask(a[k].rs, mid + 1, r, mid + 1, R);
  }
} tA, tB;
void init() {
  tA.init();
  tB.init();
  memset(A, 0, sizeof(A));
  memset(B, 0, sizeof(B));
}
int main() {
  cin >> n;
  init();
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d%d%d%d", &xA[i], &xB[i], &yA[i], &a[i], &b[i], &yB[i]);
    c[i] = (Num){xA[i] + 1, i, 1};
    c[i + n] = (Num){xB[i] + 1, i, -1};
    d[i] = xA[i] + 1;
    d[i + n] = xB[i] + 1;
  }
  c[0].x = 0;
  sort(c + 1, c + n * 2 + 1, cmp);
  sort(d + 1, d + n * 2 + 1);
  m = unique(d + 1, d + n * 2 + 1) - d - 1;
  A[0] = tA.Build(1, n, 0);
  B[0] = tB.Build(1, n, 1);
  for (int i = 1; i <= n * 2; i++)
    if (c[i].d == 1) {
      A[c[i].x] =
          tA.Update(A[c[i - 1].x], 1, n, c[i].k, b[c[i].k] - yA[c[i].k]);
      B[c[i].x] = tB.Update(B[c[i - 1].x], 1, n, c[i].k, a[c[i].k]);
    } else {
      A[c[i].x] =
          tA.Update(A[c[i - 1].x], 1, n, c[i].k, yB[c[i].k] - b[c[i].k]);
      B[c[i].x] = tB.Update(B[c[i - 1].x], 1, n, c[i].k, -a[c[i].k]);
    }
  cin >> Q;
  while (Q--) {
    int l, r;
    long long x;
    scanf("%d%d%I64d", &l, &r, &x);
    x = (x + ans) % 1000000000;
    int L = 1, R = m;
    while (L < R) {
      int mid = (L + R + 1) >> 1;
      if (d[mid] > x)
        R = mid - 1;
      else
        L = mid;
    }
    if (x < d[1]) L = 0;
    ans = tA.Ask(A[d[L]], 1, n, l, r) + tB.Ask(A[d[L]], 1, n, l, r) * x;
    printf("%I64d\n", ans);
  }
  return 0;
}

### 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;
int n, m, xA[200010], xB[200010], yA[200010], yB[200010], a[200010], b[200010],
    d[200010], Q;
int A[200010], B[200010];
long long ans = 0;
struct Num {
  int x, k, d;
} c[200010];
bool cmp(Num a, Num b) {
  if (a.x == b.x)
    return a.k < b.k;
  else
    return a.x < b.x;
}
struct Node {
  int ls, rs;
  long long s;
};
struct Tree {
  Node a[200010 * 30];
  int tot;
  void init() { tot = 0; }
  void pushup(int k) { a[k].s = a[a[k].ls].s + a[a[k].rs].s; }
  int Build(int l, int r, int q) {
    int k = ++tot;
    if (l == r) {
      a[k].ls = a[k].rs = 0;
      if (q == 0)
        a[k].s = yA[l];
      else
        a[k].s = 0;
      return k;
    }
    int mid = (l + r) >> 1;
    a[k].ls = Build(l, mid, q);
    a[k].rs = Build(mid + 1, r, q);
    pushup(k);
    return k;
  }
  int Update(int k, int l, int r, int pos, int x) {
    int nrt = ++tot;
    a[nrt] = a[k];
    if (l == r) {
      a[nrt].s += x;
      return nrt;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      a[nrt].ls = Update(a[k].ls, l, mid, pos, x);
    else
      a[nrt].rs = Update(a[k].rs, mid + 1, r, pos, x);
    pushup(nrt);
    return nrt;
  }
  long long Ask(int k, int l, int r, int L, int R) {
    if (l == L && r == R) return a[k].s;
    int mid = (l + r) >> 1;
    if (R <= mid)
      return Ask(a[k].ls, l, mid, L, R);
    else if (L > mid)
      return Ask(a[k].rs, mid + 1, r, L, R);
    else
      return Ask(a[k].ls, l, mid, L, mid) +
             Ask(a[k].rs, mid + 1, r, mid + 1, R);
  }
} tA, tB;
void init() {
  tA.init();
  tB.init();
  memset(A, 0, sizeof(A));
  memset(B, 0, sizeof(B));
}
int main() {
  cin >> n;
  init();
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d%d%d%d", &xA[i], &xB[i], &yA[i], &a[i], &b[i], &yB[i]);
    c[i] = (Num){xA[i] + 1, i, 1};
    c[i + n] = (Num){xB[i] + 1, i, -1};
    d[i] = xA[i] + 1;
    d[i + n] = xB[i] + 1;
  }
  c[0].x = 0;
  sort(c + 1, c + n * 2 + 1, cmp);
  sort(d + 1, d + n * 2 + 1);
  m = unique(d + 1, d + n * 2 + 1) - d - 1;
  A[0] = tA.Build(1, n, 0);
  B[0] = tB.Build(1, n, 1);
  for (int i = 1; i <= n * 2; i++)
    if (c[i].d == 1) {
      A[c[i].x] =
          tA.Update(A[c[i - 1].x], 1, n, c[i].k, b[c[i].k] - yA[c[i].k]);
      B[c[i].x] = tB.Update(B[c[i - 1].x], 1, n, c[i].k, a[c[i].k]);
    } else {
      A[c[i].x] =
          tA.Update(A[c[i - 1].x], 1, n, c[i].k, yB[c[i].k] - b[c[i].k]);
      B[c[i].x] = tB.Update(B[c[i - 1].x], 1, n, c[i].k, -a[c[i].k]);
    }
  cin >> Q;
  while (Q--) {
    int l, r;
    long long x;
    scanf("%d%d%I64d", &l, &r, &x);
    x = (x + ans) % 1000000000;
    int L = 1, R = m;
    while (L < R) {
      int mid = (L + R + 1) >> 1;
      if (d[mid] > x)
        R = mid - 1;
      else
        L = mid;
    }
    if (x < d[1]) L = 0;
    ans = tA.Ask(A[d[L]], 1, n, l, r) + tB.Ask(A[d[L]], 1, n, l, r) * x;
    printf("%I64d\n", ans);
  }
  return 0;
}

```