#include <bits/stdc++.h>
using namespace std;
struct fun {
  long long x[2], y[2], a, b;
  fun() {
    x[0] = y[0] = y[1] = a = b = 0;
    x[1] = 1;
  };
};
int n, q;
int m, b = 250;
int k = 200001;
long long last = 0;
long long l, r, x;
vector<fun> f;
vector<vector<long long> > z, w;
vector<long long> S;
void add(vector<long long>& z, vector<long long>& w, fun& f) {
  z[f.x[0]] += f.a;
  z[f.x[1]] -= f.a;
  w[0] += f.y[0];
  w[f.x[0]] += f.b - f.y[0];
  w[f.x[1]] += f.y[1] - f.b;
}
long long sum(long long r, long long x) {
  if (x > k) return S[r - 1];
  int p = r / b;
  long long res = (p ? z[p - 1][x] * x + w[p - 1][x] : 0);
  for (int i = p * b; i < r; ++i) {
    if (x < f[i].x[0])
      res += f[i].y[0];
    else if (x < f[i].x[1])
      res += f[i].a * x + f[i].b;
    else
      res += f[i].y[1];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  f.resize(n);
  S.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> f[i].x[0] >> f[i].x[1];
    ++f[i].x[0];
    ++f[i].x[1];
    cin >> f[i].y[0] >> f[i].a >> f[i].b >> f[i].y[1];
    S[i] = f[i].y[1] + (i ? S[i - 1] : 0);
  }
  while (n % b) f.push_back(fun()), ++n;
  m = n / b;
  z.assign(m, vector<long long>(k + 1, 0));
  w.assign(m, vector<long long>(k + 1, 0));
  for (int i = 0; i < m; ++i) {
    for (int j = i * b; j < (i + 1) * b; ++j) add(z[i], w[i], f[j]);
    for (int j = 1; j < k + 1; ++j) {
      z[i][j] += z[i][j - 1];
      w[i][j] += w[i][j - 1];
    }
    if (!i) continue;
    for (int j = 0; j < k + 1; ++j) {
      z[i][j] += z[i - 1][j];
      w[i][j] += w[i - 1][j];
    }
  }
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> l >> r >> x;
    x = (x + last) % (long long)1e9;
    last = sum(r, x) - (l > 1 ? sum(l - 1, x) : 0);
    cout << last << "\n";
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 fun {
  long long x[2], y[2], a, b;
  fun() {
    x[0] = y[0] = y[1] = a = b = 0;
    x[1] = 1;
  };
};
int n, q;
int m, b = 250;
int k = 200001;
long long last = 0;
long long l, r, x;
vector<fun> f;
vector<vector<long long> > z, w;
vector<long long> S;
void add(vector<long long>& z, vector<long long>& w, fun& f) {
  z[f.x[0]] += f.a;
  z[f.x[1]] -= f.a;
  w[0] += f.y[0];
  w[f.x[0]] += f.b - f.y[0];
  w[f.x[1]] += f.y[1] - f.b;
}
long long sum(long long r, long long x) {
  if (x > k) return S[r - 1];
  int p = r / b;
  long long res = (p ? z[p - 1][x] * x + w[p - 1][x] : 0);
  for (int i = p * b; i < r; ++i) {
    if (x < f[i].x[0])
      res += f[i].y[0];
    else if (x < f[i].x[1])
      res += f[i].a * x + f[i].b;
    else
      res += f[i].y[1];
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  f.resize(n);
  S.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> f[i].x[0] >> f[i].x[1];
    ++f[i].x[0];
    ++f[i].x[1];
    cin >> f[i].y[0] >> f[i].a >> f[i].b >> f[i].y[1];
    S[i] = f[i].y[1] + (i ? S[i - 1] : 0);
  }
  while (n % b) f.push_back(fun()), ++n;
  m = n / b;
  z.assign(m, vector<long long>(k + 1, 0));
  w.assign(m, vector<long long>(k + 1, 0));
  for (int i = 0; i < m; ++i) {
    for (int j = i * b; j < (i + 1) * b; ++j) add(z[i], w[i], f[j]);
    for (int j = 1; j < k + 1; ++j) {
      z[i][j] += z[i][j - 1];
      w[i][j] += w[i][j - 1];
    }
    if (!i) continue;
    for (int j = 0; j < k + 1; ++j) {
      z[i][j] += z[i - 1][j];
      w[i][j] += w[i - 1][j];
    }
  }
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> l >> r >> x;
    x = (x + last) % (long long)1e9;
    last = sum(r, x) - (l > 1 ? sum(l - 1, x) : 0);
    cout << last << "\n";
  }
  return 0;
}

```