#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = int(1e5) + 10;
const int MAX = int(1e9) + 1;
const int LOGN = 32;
int L[2][N * LOGN], R[2][N * LOGN], blen[2], root[2][N];
struct node {
  long long int a, b, y1, y2;
  node(int _a = 0, int _b = 0, int _y1 = 0, int _y2 = 0) {
    a = _a;
    b = _b;
    y1 = _y1;
    y2 = _y2;
  }
} ST[2][N * LOGN];
node merge(node a, node b) {
  node ret;
  ret.a = a.a + b.a;
  ret.b = a.b + b.b;
  ret.y1 = a.y1 + b.y1;
  ret.y2 = a.y2 + b.y2;
  return ret;
}
int t;
int update(int pos, node add, int l, int r, int id) {
  if (l > pos || r <= pos) return id;
  int ID = ++blen[t], m = l + (r - l) / 2;
  if (l == r - 1) return (ST[t][ID] = merge(ST[t][id], add), ID);
  L[t][ID] = update(pos, add, l, m, L[t][id]);
  R[t][ID] = update(pos, add, m, r, R[t][id]);
  return (ST[t][ID] = merge(ST[t][L[t][ID]], ST[t][R[t][ID]]), ID);
}
node dummy;
node query(int L, int R, int l, int r, int x) {
  if (r <= L || l >= R || !x) return dummy;
  if (l >= L && r <= R) return ST[t][x];
  int mid = l + (r - l) / 2;
  return merge(query(L, R, l, mid, ::L[t][x]), query(L, R, mid, r, ::R[t][x]));
}
long long int A[2][N], B[2][N], X[2][N], Y[2][N], SY[2][N];
int idx[2][N], a[N], b[N];
node sub(node a, node b) {
  a.a -= b.a;
  a.b -= b.b;
  a.y1 -= b.y1;
  a.y2 -= b.y2;
  return a;
}
long long int psa[N], psb[N];
int main() {
  int n;
  scanf("%d", &n);
  root[0][0] = ++blen[0];
  root[1][0] = ++blen[1];
  for (int i = 1; i <= n; i++) {
    int x1, x2, a, b, y1, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    t = 0;
    root[t][i] = update(x1, node(a, b, y1, y2), 0, MAX, root[t][i - 1]);
    t = 1;
    root[t][i] = update(x2, node(a, b, y1, y2), 0, MAX, root[t][i - 1]);
    psa[i] += psa[i - 1] + a;
    psb[i] += psb[i - 1] + b;
  }
  int m;
  scanf("%d", &m);
  long long int last = 0;
  for (int i = (0); i < (m); ++i) {
    int l, r, x;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &x);
    x = (x + last) % int(1e9);
    node val;
    long long int ans = 0;
    long long int sa = 0, sb = 0;
    t = 0;
    val = sub(query(x, MAX, 0, MAX, root[t][r]),
              query(x, MAX, 0, MAX, root[t][l - 1]));
    ans += val.y1;
    sa += val.a;
    sb += val.b;
    t = 1;
    val = sub(query(0, x, 0, MAX, root[t][r]),
              query(0, x, 0, MAX, root[t][l - 1]));
    ans += val.y2;
    sa += val.a;
    sb += val.b;
    long long int a = psa[r] - psa[l - 1] - sa;
    long long int b = psb[r] - psb[l - 1] - sb;
    ans += a * x + b;
    printf("%lld\n", ans);
    last = ans;
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = int(1e5) + 10;
const int MAX = int(1e9) + 1;
const int LOGN = 32;
int L[2][N * LOGN], R[2][N * LOGN], blen[2], root[2][N];
struct node {
  long long int a, b, y1, y2;
  node(int _a = 0, int _b = 0, int _y1 = 0, int _y2 = 0) {
    a = _a;
    b = _b;
    y1 = _y1;
    y2 = _y2;
  }
} ST[2][N * LOGN];
node merge(node a, node b) {
  node ret;
  ret.a = a.a + b.a;
  ret.b = a.b + b.b;
  ret.y1 = a.y1 + b.y1;
  ret.y2 = a.y2 + b.y2;
  return ret;
}
int t;
int update(int pos, node add, int l, int r, int id) {
  if (l > pos || r <= pos) return id;
  int ID = ++blen[t], m = l + (r - l) / 2;
  if (l == r - 1) return (ST[t][ID] = merge(ST[t][id], add), ID);
  L[t][ID] = update(pos, add, l, m, L[t][id]);
  R[t][ID] = update(pos, add, m, r, R[t][id]);
  return (ST[t][ID] = merge(ST[t][L[t][ID]], ST[t][R[t][ID]]), ID);
}
node dummy;
node query(int L, int R, int l, int r, int x) {
  if (r <= L || l >= R || !x) return dummy;
  if (l >= L && r <= R) return ST[t][x];
  int mid = l + (r - l) / 2;
  return merge(query(L, R, l, mid, ::L[t][x]), query(L, R, mid, r, ::R[t][x]));
}
long long int A[2][N], B[2][N], X[2][N], Y[2][N], SY[2][N];
int idx[2][N], a[N], b[N];
node sub(node a, node b) {
  a.a -= b.a;
  a.b -= b.b;
  a.y1 -= b.y1;
  a.y2 -= b.y2;
  return a;
}
long long int psa[N], psb[N];
int main() {
  int n;
  scanf("%d", &n);
  root[0][0] = ++blen[0];
  root[1][0] = ++blen[1];
  for (int i = 1; i <= n; i++) {
    int x1, x2, a, b, y1, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    t = 0;
    root[t][i] = update(x1, node(a, b, y1, y2), 0, MAX, root[t][i - 1]);
    t = 1;
    root[t][i] = update(x2, node(a, b, y1, y2), 0, MAX, root[t][i - 1]);
    psa[i] += psa[i - 1] + a;
    psb[i] += psb[i - 1] + b;
  }
  int m;
  scanf("%d", &m);
  long long int last = 0;
  for (int i = (0); i < (m); ++i) {
    int l, r, x;
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &x);
    x = (x + last) % int(1e9);
    node val;
    long long int ans = 0;
    long long int sa = 0, sb = 0;
    t = 0;
    val = sub(query(x, MAX, 0, MAX, root[t][r]),
              query(x, MAX, 0, MAX, root[t][l - 1]));
    ans += val.y1;
    sa += val.a;
    sb += val.b;
    t = 1;
    val = sub(query(0, x, 0, MAX, root[t][r]),
              query(0, x, 0, MAX, root[t][l - 1]));
    ans += val.y2;
    sa += val.a;
    sb += val.b;
    long long int a = psa[r] - psa[l - 1] - sa;
    long long int b = psb[r] - psb[l - 1] - sb;
    ans += a * x + b;
    printf("%lld\n", ans);
    last = ans;
  }
  return 0;
}

```