#include <bits/stdc++.h>
using namespace std;
constexpr int N = 75000 * 2;
constexpr int H = 18;
int a[N], tmp[N], wav[H][N + 1];
struct L {
  long long a, b;
};
L ls[H + 1][N + 1];
void build(int l, int r, int d) {
  if (d == H || r - l == 0) return;
  int m = l;
  for (int i = l; i < r; i++) {
    tmp[i] = a[i];
    bool b = a[i] >> H - 1 - d & 1;
    wav[d][i + 1] = wav[d][i] + b;
    m += !b;
  }
  int ll = l;
  int mm = m;
  for (int i = l; i < r; i++) {
    int &k = wav[d][i + 1] - wav[d][i] == 0 ? ll : mm;
    a[k] = tmp[i];
    ls[d + 1][k + 1] = ls[d][i + 1];
    k++;
  }
  build(l, m, d + 1);
  build(m, r, d + 1);
}
int count1(int d, int l, int r) { return wav[d][r] - wav[d][l]; }
int count0(int d, int l, int r) { return (r - l) - count1(d, l, r); }
long long sum(int l, int r, long long x, int k) {
  int ll = 0;
  int rr = N;
  long long ret = 0;
  for (int i = 0; i < H; i++) {
    int mm = count0(i, ll, rr) + ll;
    int l0 = count0(i, ll, l) + ll;
    int r0 = count0(i, ll, r) + ll;
    if (k < 1 << H - 1 - i) {
      l = l0;
      r = r0;
      rr = mm;
    } else {
      ret += ls[i + 1][r0].a * x + ls[i + 1][r0].b;
      ret -= ls[i + 1][l0].a * x + ls[i + 1][l0].b;
      l = count1(i, ll, l) + mm;
      r = count1(i, ll, r) + mm;
      k -= 1 << H - 1 - i;
      ll = mm;
    }
  }
  return ret;
}
int main() {
  int n;
  cin >> n;
  vector<long long> base(n + 1);
  for (int i = 0; i < n; i++) {
    int x1, x2, y1, A, B, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &A, &B, &y2);
    base[i + 1] = y1;
    a[i * 2] = x1;
    a[i * 2 + 1] = x2;
    ls[0][i * 2 + 1] = (L){A, -y1 + B};
    ls[0][i * 2 + 2] = (L){-A, -B + y2};
  }
  for (int i = 0; i < n; i++) {
    base[i + 1] += base[i];
  }
  build(0, N, 0);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < N; j++) {
      ls[i + 1][j + 1].a += ls[i + 1][j].a;
      ls[i + 1][j + 1].b += ls[i + 1][j].b;
    }
  }
  long long last = 0;
  int q;
  cin >> q;
  while (q--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    l--;
    int xi = (x + last) % int(1e9);
    int t = min(xi, 200005);
    last = sum(l * 2, r * 2, xi, t) + base[r] - base[l];
    printf("%lld\n", last);
  }
}

### Prompt

Create a solution in cpp for 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;
constexpr int N = 75000 * 2;
constexpr int H = 18;
int a[N], tmp[N], wav[H][N + 1];
struct L {
  long long a, b;
};
L ls[H + 1][N + 1];
void build(int l, int r, int d) {
  if (d == H || r - l == 0) return;
  int m = l;
  for (int i = l; i < r; i++) {
    tmp[i] = a[i];
    bool b = a[i] >> H - 1 - d & 1;
    wav[d][i + 1] = wav[d][i] + b;
    m += !b;
  }
  int ll = l;
  int mm = m;
  for (int i = l; i < r; i++) {
    int &k = wav[d][i + 1] - wav[d][i] == 0 ? ll : mm;
    a[k] = tmp[i];
    ls[d + 1][k + 1] = ls[d][i + 1];
    k++;
  }
  build(l, m, d + 1);
  build(m, r, d + 1);
}
int count1(int d, int l, int r) { return wav[d][r] - wav[d][l]; }
int count0(int d, int l, int r) { return (r - l) - count1(d, l, r); }
long long sum(int l, int r, long long x, int k) {
  int ll = 0;
  int rr = N;
  long long ret = 0;
  for (int i = 0; i < H; i++) {
    int mm = count0(i, ll, rr) + ll;
    int l0 = count0(i, ll, l) + ll;
    int r0 = count0(i, ll, r) + ll;
    if (k < 1 << H - 1 - i) {
      l = l0;
      r = r0;
      rr = mm;
    } else {
      ret += ls[i + 1][r0].a * x + ls[i + 1][r0].b;
      ret -= ls[i + 1][l0].a * x + ls[i + 1][l0].b;
      l = count1(i, ll, l) + mm;
      r = count1(i, ll, r) + mm;
      k -= 1 << H - 1 - i;
      ll = mm;
    }
  }
  return ret;
}
int main() {
  int n;
  cin >> n;
  vector<long long> base(n + 1);
  for (int i = 0; i < n; i++) {
    int x1, x2, y1, A, B, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &A, &B, &y2);
    base[i + 1] = y1;
    a[i * 2] = x1;
    a[i * 2 + 1] = x2;
    ls[0][i * 2 + 1] = (L){A, -y1 + B};
    ls[0][i * 2 + 2] = (L){-A, -B + y2};
  }
  for (int i = 0; i < n; i++) {
    base[i + 1] += base[i];
  }
  build(0, N, 0);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < N; j++) {
      ls[i + 1][j + 1].a += ls[i + 1][j].a;
      ls[i + 1][j + 1].b += ls[i + 1][j].b;
    }
  }
  long long last = 0;
  int q;
  cin >> q;
  while (q--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    l--;
    int xi = (x + last) % int(1e9);
    int t = min(xi, 200005);
    last = sum(l * 2, r * 2, xi, t) + base[r] - base[l];
    printf("%lld\n", last);
  }
}

```