#include <bits/stdc++.h>
using namespace std;
constexpr int N = 75000 * 2;
constexpr int H = 18;
struct foo {
  int key;
  long long a, b;
};
foo dat[N], mat[H][N + 1];
void build(int l, int r, int d) {
  if (d == H || r - l == 0) return;
  for (int i = l; i < r; i++) {
    mat[d][i + 1].key = mat[d][i].key + (dat[i].key >> H - 1 - d & 1);
  }
  int m = stable_partition(dat + l, dat + r,
                           [&](foo x) { return ~x.key >> (H - 1 - d) & 1; }) -
          dat;
  for (int i = l; i < r; i++) {
    mat[d][i + 1].a = mat[d][i].a + dat[i].a;
    mat[d][i + 1].b = mat[d][i].b + dat[i].b;
  }
  build(l, m, d + 1);
  build(m, r, d + 1);
}
int count1(int d, int l, int r) { return mat[d][r].key - mat[d][l].key; }
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, 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 >> H - 1 - i & 1) {
      l = l0;
      r = r0;
      rr = mm;
    } else {
      ret += mat[i][r0].a * x + mat[i][r0].b;
      ret -= mat[i][l0].a * x + mat[i][l0].b;
      l = count1(i, ll, l) + mm;
      r = count1(i, ll, r) + mm;
      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] = base[i] + y1;
    dat[i * 2 + 0] = {x1, A, -y1 + B};
    dat[i * 2 + 1] = {x2, -A, -B + y2};
  }
  build(0, N, 0);
  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;
struct foo {
  int key;
  long long a, b;
};
foo dat[N], mat[H][N + 1];
void build(int l, int r, int d) {
  if (d == H || r - l == 0) return;
  for (int i = l; i < r; i++) {
    mat[d][i + 1].key = mat[d][i].key + (dat[i].key >> H - 1 - d & 1);
  }
  int m = stable_partition(dat + l, dat + r,
                           [&](foo x) { return ~x.key >> (H - 1 - d) & 1; }) -
          dat;
  for (int i = l; i < r; i++) {
    mat[d][i + 1].a = mat[d][i].a + dat[i].a;
    mat[d][i + 1].b = mat[d][i].b + dat[i].b;
  }
  build(l, m, d + 1);
  build(m, r, d + 1);
}
int count1(int d, int l, int r) { return mat[d][r].key - mat[d][l].key; }
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, 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 >> H - 1 - i & 1) {
      l = l0;
      r = r0;
      rr = mm;
    } else {
      ret += mat[i][r0].a * x + mat[i][r0].b;
      ret -= mat[i][l0].a * x + mat[i][l0].b;
      l = count1(i, ll, l) + mm;
      r = count1(i, ll, r) + mm;
      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] = base[i] + y1;
    dat[i * 2 + 0] = {x1, A, -y1 + B};
    dat[i * 2 + 1] = {x2, -A, -B + y2};
  }
  build(0, N, 0);
  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);
  }
}

```