#include <bits/stdc++.h>
using namespace std;
const int MOD = int(1e9);
int n;
int lo[75000], hi[75000], loy[75000], a[75000], b[75000], hiy[75000];
int m;
int from, to, x;
struct S {
  int key;
  long long a, b, c;
  S(int key, long long a, long long b, long long c)
      : key(key), a(a), b(b), c(c) {}
  inline bool operator<(const S &rhs) const { return key < rhs.key; }
};
vector<S> sx1[1 << 18], sx2[1 << 18];
vector<int> ix1[1 << 18], ix2[1 << 18];
long long suma[1 << 18], sumb[1 << 18];
const int off = 1 << 17;
void stBuild() {
  for (int i = 0; i < (int)(n); ++i)
    for (int j = off + i; j >= 1; j >>= 1) {
      sx1[j].push_back(S(-lo[i], a[i], b[i], loy[i]));
      sx2[j].push_back(S(hi[i], a[i], b[i], hiy[i]));
      suma[j] += a[i];
      sumb[j] += b[i];
    }
  for (int i = 0; i < (int)(2 * off); ++i) {
    sort(sx1[i].begin(), sx1[i].end());
    sort(sx2[i].begin(), sx2[i].end());
    long long pa = 0, push_back = 0, pc = 0;
    for (S &s : sx1[i]) {
      ix1[i].push_back(s.key);
      pa += s.a;
      push_back += s.b;
      pc += s.c;
      s.a = pa;
      s.b = push_back;
      s.c = pc;
    }
    pa = 0, push_back = 0, pc = 0;
    for (S &s : sx2[i]) {
      ix2[i].push_back(s.key);
      pa += s.a;
      push_back += s.b;
      pc += s.c;
      s.a = pa;
      s.b = push_back;
      s.c = pc;
    }
  }
}
long long xi;
long long stGet(int v, int L, int R, int l, int r) {
  if (l > r) return 0;
  if (l == L && r == R) {
    long long sa = suma[v];
    long long sb = sumb[v];
    int ind =
        lower_bound(ix1[v].begin(), ix1[v].end(), -xi + 1) - ix1[v].begin();
    long long res = (ind == 0 ? 0ll : sx1[v][ind - 1].c);
    sa -= (ind == 0 ? 0ll : sx1[v][ind - 1].a);
    sb -= (ind == 0 ? 0ll : sx1[v][ind - 1].b);
    ind = lower_bound(ix2[v].begin(), ix2[v].end(), xi) - ix2[v].begin();
    res += (ind == 0 ? 0ll : sx2[v][ind - 1].c);
    sa -= (ind == 0 ? 0ll : sx2[v][ind - 1].a);
    sb -= (ind == 0 ? 0ll : sx2[v][ind - 1].b);
    res += sa * xi + sb;
    return res;
  }
  int mid = (L + R) >> 1;
  return stGet(2 * v, L, mid, l, min(r, mid)) +
         stGet(2 * v + 1, mid + 1, R, max(l, mid + 1), r);
}
long long solve(int from, int to, int x) {
  xi = x;
  return stGet(1, 0, off - 1, from, to);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < (int)(n); ++i) {
    cin >> lo[i] >> hi[i] >> loy[i] >> a[i] >> b[i] >> hiy[i];
  }
  stBuild();
  cin >> m;
  int last = 0;
  for (int i = 0; i < (int)(m); ++i) {
    cin >> from >> to >> x;
    --from, --to;
    x = (x + last) % MOD;
    long long ans = solve(from, to, x);
    last = ans % MOD;
    cout << ans << '\n';
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
const int MOD = int(1e9);
int n;
int lo[75000], hi[75000], loy[75000], a[75000], b[75000], hiy[75000];
int m;
int from, to, x;
struct S {
  int key;
  long long a, b, c;
  S(int key, long long a, long long b, long long c)
      : key(key), a(a), b(b), c(c) {}
  inline bool operator<(const S &rhs) const { return key < rhs.key; }
};
vector<S> sx1[1 << 18], sx2[1 << 18];
vector<int> ix1[1 << 18], ix2[1 << 18];
long long suma[1 << 18], sumb[1 << 18];
const int off = 1 << 17;
void stBuild() {
  for (int i = 0; i < (int)(n); ++i)
    for (int j = off + i; j >= 1; j >>= 1) {
      sx1[j].push_back(S(-lo[i], a[i], b[i], loy[i]));
      sx2[j].push_back(S(hi[i], a[i], b[i], hiy[i]));
      suma[j] += a[i];
      sumb[j] += b[i];
    }
  for (int i = 0; i < (int)(2 * off); ++i) {
    sort(sx1[i].begin(), sx1[i].end());
    sort(sx2[i].begin(), sx2[i].end());
    long long pa = 0, push_back = 0, pc = 0;
    for (S &s : sx1[i]) {
      ix1[i].push_back(s.key);
      pa += s.a;
      push_back += s.b;
      pc += s.c;
      s.a = pa;
      s.b = push_back;
      s.c = pc;
    }
    pa = 0, push_back = 0, pc = 0;
    for (S &s : sx2[i]) {
      ix2[i].push_back(s.key);
      pa += s.a;
      push_back += s.b;
      pc += s.c;
      s.a = pa;
      s.b = push_back;
      s.c = pc;
    }
  }
}
long long xi;
long long stGet(int v, int L, int R, int l, int r) {
  if (l > r) return 0;
  if (l == L && r == R) {
    long long sa = suma[v];
    long long sb = sumb[v];
    int ind =
        lower_bound(ix1[v].begin(), ix1[v].end(), -xi + 1) - ix1[v].begin();
    long long res = (ind == 0 ? 0ll : sx1[v][ind - 1].c);
    sa -= (ind == 0 ? 0ll : sx1[v][ind - 1].a);
    sb -= (ind == 0 ? 0ll : sx1[v][ind - 1].b);
    ind = lower_bound(ix2[v].begin(), ix2[v].end(), xi) - ix2[v].begin();
    res += (ind == 0 ? 0ll : sx2[v][ind - 1].c);
    sa -= (ind == 0 ? 0ll : sx2[v][ind - 1].a);
    sb -= (ind == 0 ? 0ll : sx2[v][ind - 1].b);
    res += sa * xi + sb;
    return res;
  }
  int mid = (L + R) >> 1;
  return stGet(2 * v, L, mid, l, min(r, mid)) +
         stGet(2 * v + 1, mid + 1, R, max(l, mid + 1), r);
}
long long solve(int from, int to, int x) {
  xi = x;
  return stGet(1, 0, off - 1, from, to);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < (int)(n); ++i) {
    cin >> lo[i] >> hi[i] >> loy[i] >> a[i] >> b[i] >> hiy[i];
  }
  stBuild();
  cin >> m;
  int last = 0;
  for (int i = 0; i < (int)(m); ++i) {
    cin >> from >> to >> x;
    --from, --to;
    x = (x + last) % MOD;
    long long ans = solve(from, to, x);
    last = ans % MOD;
    cout << ans << '\n';
  }
  return 0;
}

```