#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int NX = 200002;
const int MAXLG = 18;
const int MAXN = 75000;
const int MAXS = 8 * MAXLG * MAXN + 4 * NX;
int ns;
long long sa[MAXS], sb[MAXS];
int sl[MAXS], sr[MAXS];
int smake(long long a, long long b) {
  assert(ns < MAXS);
  sa[ns] = a, sb[ns] = b, sl[ns] = -1, sr[ns] = -1;
  return ns++;
}
int smake(long long a, long long b, int nl, int nr) {
  int ret = smake(a, b);
  sl[ret] = nl, sr[ret] = nr;
  return ret;
}
int sbuild(int l, int r) {
  int ret = smake(0, 0);
  if (l == r) return ret;
  int m = l + (r - l) / 2;
  sl[ret] = sbuild(l, m), sr[ret] = sbuild(m + 1, r);
  return ret;
}
int smod(int x, int l, int r, int X1, int X2, int Y1, int Y2, int A, int B) {
  if (r <= X1) return smake(sa[x], sb[x] + Y1, sl[x], sr[x]);
  if (l > X2) return smake(sa[x], sb[x] + Y2, sl[x], sr[x]);
  if (X1 < l && r <= X2) return smake(sa[x] + A, sb[x] + B, sl[x], sr[x]);
  int m = l + (r - l) / 2;
  int ret = smake(sa[x], sb[x]);
  sl[ret] = smod(sl[x], l, m, X1, X2, Y1, Y2, A, B);
  sr[ret] = smod(sr[x], m + 1, r, X1, X2, Y1, Y2, A, B);
  return ret;
}
pair<long long, long long> squery(int x, int l, int r, int X) {
  if (l == r) return make_pair(sa[x], sb[x]);
  int m = l + (r - l) / 2;
  pair<long long, long long> cur =
      X <= m ? squery(sl[x], l, m, X) : squery(sr[x], m + 1, r, X);
  return make_pair(cur.first + sa[x], cur.second + sb[x]);
}
int n, nq;
int root[MAXN + 1];
void run() {
  ns = 0;
  root[0] = sbuild(0, NX - 1);
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) {
    int x1, x2, y1, y2, a, b;
    scanf("%d%d%d%d%d%d", &x1, &x2, &y1, &a, &b, &y2);
    root[i + 1] = smod(root[i], 0, NX - 1, x1, x2, y1, y2, a, b);
  }
  scanf("%d", &nq);
  long long last = 0;
  for (int i = (0); i < (nq); ++i) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    --l, --r, x = min((int)((x + last) % 1000000000), NX - 1);
    pair<long long, long long> qr = squery(root[r + 1], 0, NX - 1, x),
                               ql = squery(root[l], 0, NX - 1, x);
    long long a = qr.first - ql.first, b = qr.second - ql.second;
    long long ans = a * x + b;
    printf("%lld\n", ans);
    last = ans;
  }
}
int main() {
  run();
  return 0;
}

### Prompt

Your task is to create a CPP solution 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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int NX = 200002;
const int MAXLG = 18;
const int MAXN = 75000;
const int MAXS = 8 * MAXLG * MAXN + 4 * NX;
int ns;
long long sa[MAXS], sb[MAXS];
int sl[MAXS], sr[MAXS];
int smake(long long a, long long b) {
  assert(ns < MAXS);
  sa[ns] = a, sb[ns] = b, sl[ns] = -1, sr[ns] = -1;
  return ns++;
}
int smake(long long a, long long b, int nl, int nr) {
  int ret = smake(a, b);
  sl[ret] = nl, sr[ret] = nr;
  return ret;
}
int sbuild(int l, int r) {
  int ret = smake(0, 0);
  if (l == r) return ret;
  int m = l + (r - l) / 2;
  sl[ret] = sbuild(l, m), sr[ret] = sbuild(m + 1, r);
  return ret;
}
int smod(int x, int l, int r, int X1, int X2, int Y1, int Y2, int A, int B) {
  if (r <= X1) return smake(sa[x], sb[x] + Y1, sl[x], sr[x]);
  if (l > X2) return smake(sa[x], sb[x] + Y2, sl[x], sr[x]);
  if (X1 < l && r <= X2) return smake(sa[x] + A, sb[x] + B, sl[x], sr[x]);
  int m = l + (r - l) / 2;
  int ret = smake(sa[x], sb[x]);
  sl[ret] = smod(sl[x], l, m, X1, X2, Y1, Y2, A, B);
  sr[ret] = smod(sr[x], m + 1, r, X1, X2, Y1, Y2, A, B);
  return ret;
}
pair<long long, long long> squery(int x, int l, int r, int X) {
  if (l == r) return make_pair(sa[x], sb[x]);
  int m = l + (r - l) / 2;
  pair<long long, long long> cur =
      X <= m ? squery(sl[x], l, m, X) : squery(sr[x], m + 1, r, X);
  return make_pair(cur.first + sa[x], cur.second + sb[x]);
}
int n, nq;
int root[MAXN + 1];
void run() {
  ns = 0;
  root[0] = sbuild(0, NX - 1);
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) {
    int x1, x2, y1, y2, a, b;
    scanf("%d%d%d%d%d%d", &x1, &x2, &y1, &a, &b, &y2);
    root[i + 1] = smod(root[i], 0, NX - 1, x1, x2, y1, y2, a, b);
  }
  scanf("%d", &nq);
  long long last = 0;
  for (int i = (0); i < (nq); ++i) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    --l, --r, x = min((int)((x + last) % 1000000000), NX - 1);
    pair<long long, long long> qr = squery(root[r + 1], 0, NX - 1, x),
                               ql = squery(root[l], 0, NX - 1, x);
    long long a = qr.first - ql.first, b = qr.second - ql.second;
    long long ans = a * x + b;
    printf("%lld\n", ans);
    last = ans;
  }
}
int main() {
  run();
  return 0;
}

```