#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:1048576")
using namespace std;
int IT_MAX = 1 << 18;
const long long MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 3234567890123456789ll;
const double PI = acos(-1);
const double EPS = 1e-8;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
int nc = 1;
int son[6000000][2];
pair<long long, long long> val[6000000];
int update(int st, int en, int p, int n, pair<long long, long long> v) {
  if (st == en) {
    nc++;
    val[nc] = v;
    return nc;
  }
  int nn = ++nc;
  son[nn][0] = son[n][0], son[nn][1] = son[n][1];
  int mi = (st + en) / 2;
  if (p <= mi)
    son[nn][0] = update(st, mi, p, son[n][0], v);
  else
    son[nn][1] = update(mi + 1, en, p, son[n][1], v);
  val[nn] = val[son[nn][0]] + val[son[nn][1]];
  return nn;
}
pair<long long, long long> getsum(int st, int en, int S, int E, int n) {
  if (n == 0) return pair<long long, long long>(0, 0);
  if (st > en) return pair<long long, long long>(0, 0);
  if (st == S && en == E) return val[n];
  int M = (S + E) / 2;
  return getsum(st, min(en, M), S, M, son[n][0]) +
         getsum(max(st, M + 1), en, M + 1, E, son[n][1]);
}
long long in[300050][3];
int u[300050];
int R[300050];
int main() {
  int N, i;
  scanf("%d", &N);
  for (i = 1; i <= N; i++) {
    int x1, x2, y1, a, b, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    in[3 * i - 2][0] = 0, in[3 * i - 2][1] = 0, in[3 * i - 2][2] = y1;
    in[3 * i - 1][0] = x1 + 1, in[3 * i - 1][1] = a, in[3 * i - 1][2] = b - y1;
    in[3 * i][0] = x2 + 1, in[3 * i][1] = -a, in[3 * i][2] = -b + y2;
  }
  for (i = 1; i <= 3 * N; i++) u[i] = i;
  sort(u + 1, u + 3 * N + 1, [](int a, int b) { return in[a][0] < in[b][0]; });
  int p = 1;
  for (i = 0; i <= 300000; i++) {
    R[i] = 1;
    if (i) R[i] = R[i - 1];
    while (p <= 3 * N) {
      int t = u[p];
      if (in[t][0] > i) break;
      R[i] = update(1, IT_MAX, t, R[i],
                    pair<long long, long long>(in[t][1], in[t][2]));
      p++;
    }
  }
  int Q;
  long long last = 0;
  scanf("%d", &Q);
  while (Q--) {
    int l, r;
    long long x;
    scanf("%d %d %lld", &l, &r, &x);
    x = (x + last) % 1000000000;
    long long nx = min(x, 300000ll);
    pair<long long, long long> u = getsum(3 * l - 2, 3 * r, 1, IT_MAX, R[nx]);
    last = u.first * x + u.second;
    printf("%lld\n", last);
  }
  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>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:1048576")
using namespace std;
int IT_MAX = 1 << 18;
const long long MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 3234567890123456789ll;
const double PI = acos(-1);
const double EPS = 1e-8;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
int nc = 1;
int son[6000000][2];
pair<long long, long long> val[6000000];
int update(int st, int en, int p, int n, pair<long long, long long> v) {
  if (st == en) {
    nc++;
    val[nc] = v;
    return nc;
  }
  int nn = ++nc;
  son[nn][0] = son[n][0], son[nn][1] = son[n][1];
  int mi = (st + en) / 2;
  if (p <= mi)
    son[nn][0] = update(st, mi, p, son[n][0], v);
  else
    son[nn][1] = update(mi + 1, en, p, son[n][1], v);
  val[nn] = val[son[nn][0]] + val[son[nn][1]];
  return nn;
}
pair<long long, long long> getsum(int st, int en, int S, int E, int n) {
  if (n == 0) return pair<long long, long long>(0, 0);
  if (st > en) return pair<long long, long long>(0, 0);
  if (st == S && en == E) return val[n];
  int M = (S + E) / 2;
  return getsum(st, min(en, M), S, M, son[n][0]) +
         getsum(max(st, M + 1), en, M + 1, E, son[n][1]);
}
long long in[300050][3];
int u[300050];
int R[300050];
int main() {
  int N, i;
  scanf("%d", &N);
  for (i = 1; i <= N; i++) {
    int x1, x2, y1, a, b, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    in[3 * i - 2][0] = 0, in[3 * i - 2][1] = 0, in[3 * i - 2][2] = y1;
    in[3 * i - 1][0] = x1 + 1, in[3 * i - 1][1] = a, in[3 * i - 1][2] = b - y1;
    in[3 * i][0] = x2 + 1, in[3 * i][1] = -a, in[3 * i][2] = -b + y2;
  }
  for (i = 1; i <= 3 * N; i++) u[i] = i;
  sort(u + 1, u + 3 * N + 1, [](int a, int b) { return in[a][0] < in[b][0]; });
  int p = 1;
  for (i = 0; i <= 300000; i++) {
    R[i] = 1;
    if (i) R[i] = R[i - 1];
    while (p <= 3 * N) {
      int t = u[p];
      if (in[t][0] > i) break;
      R[i] = update(1, IT_MAX, t, R[i],
                    pair<long long, long long>(in[t][1], in[t][2]));
      p++;
    }
  }
  int Q;
  long long last = 0;
  scanf("%d", &Q);
  while (Q--) {
    int l, r;
    long long x;
    scanf("%d %d %lld", &l, &r, &x);
    x = (x + last) % 1000000000;
    long long nx = min(x, 300000ll);
    pair<long long, long long> u = getsum(3 * l - 2, 3 * r, 1, IT_MAX, R[nx]);
    last = u.first * x + u.second;
    printf("%lld\n", last);
  }
  return 0;
}

```