#include <bits/stdc++.h>
using namespace std;
struct node {
  node *l = nullptr;
  node *r = nullptr;
  long long val = 0;
};
constexpr int N = 1 << 18;
long long sum(node *x) { return x ? x->val : 0LL; }
node *update(int k, long long v, node *x, int l = 0, int r = N) {
  x = x ? new node(*x) : new node();
  if (r - l == 1) {
    x->val = v;
    return x;
  }
  int m = l + r >> 1;
  if (k < m) {
    x->l = update(k, v, x->l, l, m);
  } else {
    x->r = update(k, v, x->r, m, r);
  }
  x->val = sum(x->l) + sum(x->r);
  return x;
}
long long query(int a, int b, node *x, int l = 0, int r = N) {
  if (!x) return 0;
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return sum(x);
  int m = (l + r) / 2;
  return query(a, b, x->l, l, m) + query(a, b, x->r, m, r);
}
int main() {
  int n;
  cin >> n;
  vector<int> x1(n), x2(n), y1(n), y2(n), a(n), b(n);
  vector<node *> A(200010), B(200010);
  vector<vector<int>> add(200010);
  vector<vector<int>> del(200010);
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d%d%d%d", &x1[i], &x2[i], &y1[i], &a[i], &b[i], &y2[i]);
    B[0] = update(i, y1[i], B[0]);
    del[x1[i] + 1].push_back(i);
    add[x2[i] + 1].push_back(i);
  }
  for (int i = 1; i <= 200005; i++) {
    A[i] = A[i - 1];
    B[i] = B[i - 1];
    for (int id : del[i]) {
      A[i] = update(id, a[id], A[i]);
      B[i] = update(id, b[id], B[i]);
    }
    for (int id : add[i]) {
      A[i] = update(id, 0, A[i]);
      B[i] = update(id, y2[id], B[i]);
    }
  }
  int q;
  cin >> q;
  long long last = 0;
  constexpr long long mod = 1e9;
  while (q--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    long long xi = (x + last) % mod;
    long long t = min(xi, 200002LL);
    l--;
    long long aa = query(l, r, A[t]);
    long long bb = query(l, r, B[t]);
    last = aa * xi + bb;
    printf("%lld\n", last);
  }
}

### 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>
using namespace std;
struct node {
  node *l = nullptr;
  node *r = nullptr;
  long long val = 0;
};
constexpr int N = 1 << 18;
long long sum(node *x) { return x ? x->val : 0LL; }
node *update(int k, long long v, node *x, int l = 0, int r = N) {
  x = x ? new node(*x) : new node();
  if (r - l == 1) {
    x->val = v;
    return x;
  }
  int m = l + r >> 1;
  if (k < m) {
    x->l = update(k, v, x->l, l, m);
  } else {
    x->r = update(k, v, x->r, m, r);
  }
  x->val = sum(x->l) + sum(x->r);
  return x;
}
long long query(int a, int b, node *x, int l = 0, int r = N) {
  if (!x) return 0;
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return sum(x);
  int m = (l + r) / 2;
  return query(a, b, x->l, l, m) + query(a, b, x->r, m, r);
}
int main() {
  int n;
  cin >> n;
  vector<int> x1(n), x2(n), y1(n), y2(n), a(n), b(n);
  vector<node *> A(200010), B(200010);
  vector<vector<int>> add(200010);
  vector<vector<int>> del(200010);
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d%d%d%d", &x1[i], &x2[i], &y1[i], &a[i], &b[i], &y2[i]);
    B[0] = update(i, y1[i], B[0]);
    del[x1[i] + 1].push_back(i);
    add[x2[i] + 1].push_back(i);
  }
  for (int i = 1; i <= 200005; i++) {
    A[i] = A[i - 1];
    B[i] = B[i - 1];
    for (int id : del[i]) {
      A[i] = update(id, a[id], A[i]);
      B[i] = update(id, b[id], B[i]);
    }
    for (int id : add[i]) {
      A[i] = update(id, 0, A[i]);
      B[i] = update(id, y2[id], B[i]);
    }
  }
  int q;
  cin >> q;
  long long last = 0;
  constexpr long long mod = 1e9;
  while (q--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    long long xi = (x + last) % mod;
    long long t = min(xi, 200002LL);
    l--;
    long long aa = query(l, r, A[t]);
    long long bb = query(l, r, B[t]);
    last = aa * xi + bb;
    printf("%lld\n", last);
  }
}

```