#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T x, T y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    T f = x % y;
    x = y;
    y = f;
  }
  return x;
}
struct Node {
  Node *l, *r;
  long long a, b;
  Node() : l(NULL), r(NULL), a(0), b(0) {}
};
Node* makeTree(int fr, int to) {
  Node* node = new Node();
  if (fr == to) return node;
  int m = (fr + to) / 2;
  node->l = makeTree(fr, m);
  node->r = makeTree(m + 1, to);
  return node;
}
Node* update(Node* _node, int fr, int to, int x1, int x2, long long a,
             long long b) {
  if (x2 < fr || x1 > to) return _node;
  Node* node = new Node();
  *node = *_node;
  if (x1 <= fr && to <= x2) {
    node->a += a;
    node->b += b;
    return node;
  }
  int m = (fr + to) / 2;
  node->l = update(node->l, fr, m, x1, x2, a, b);
  node->r = update(node->r, m + 1, to, x1, x2, a, b);
  return node;
}
long long query(Node* node, int fr, int to, long long x) {
  long long res = node->a * x + node->b;
  if (fr == to) return res;
  int m = (fr + to) / 2;
  if (x <= m)
    return res + query(node->l, fr, m, x);
  else
    return res + query(node->r, m + 1, to, x);
}
Node* froot[75007];
const int maxx = 200002;
int main(int argc, char* argv[]) {
  int n;
  std::cin.sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n;
  {
    froot[0] = makeTree(0, maxx);
    for (int i = 1; i <= n; i++) {
      int x1, x2, y1, a, b, y2;
      cin >> x1 >> x2 >> y1 >> a >> b >> y2;
      froot[i] = update(froot[i - 1], 0, maxx, 0, x1, 0, y1);
      froot[i] = update(froot[i], 0, maxx, x1 + 1, x2, a, b);
      froot[i] = update(froot[i], 0, maxx, x2 + 1, maxx, 0, y2);
    }
    int m;
    cin >> m;
    long long last = 0;
    while (m--) {
      int l, r, x;
      cin >> l >> r >> x;
      last = (last + x) % 1000000000ll;
      last =
          query(froot[r], 0, maxx, last) - query(froot[l - 1], 0, maxx, last);
      cout << last << endl;
    }
  }
  return 0;
}

### 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;
template <typename T>
T gcd(T x, T y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    T f = x % y;
    x = y;
    y = f;
  }
  return x;
}
struct Node {
  Node *l, *r;
  long long a, b;
  Node() : l(NULL), r(NULL), a(0), b(0) {}
};
Node* makeTree(int fr, int to) {
  Node* node = new Node();
  if (fr == to) return node;
  int m = (fr + to) / 2;
  node->l = makeTree(fr, m);
  node->r = makeTree(m + 1, to);
  return node;
}
Node* update(Node* _node, int fr, int to, int x1, int x2, long long a,
             long long b) {
  if (x2 < fr || x1 > to) return _node;
  Node* node = new Node();
  *node = *_node;
  if (x1 <= fr && to <= x2) {
    node->a += a;
    node->b += b;
    return node;
  }
  int m = (fr + to) / 2;
  node->l = update(node->l, fr, m, x1, x2, a, b);
  node->r = update(node->r, m + 1, to, x1, x2, a, b);
  return node;
}
long long query(Node* node, int fr, int to, long long x) {
  long long res = node->a * x + node->b;
  if (fr == to) return res;
  int m = (fr + to) / 2;
  if (x <= m)
    return res + query(node->l, fr, m, x);
  else
    return res + query(node->r, m + 1, to, x);
}
Node* froot[75007];
const int maxx = 200002;
int main(int argc, char* argv[]) {
  int n;
  std::cin.sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> n;
  {
    froot[0] = makeTree(0, maxx);
    for (int i = 1; i <= n; i++) {
      int x1, x2, y1, a, b, y2;
      cin >> x1 >> x2 >> y1 >> a >> b >> y2;
      froot[i] = update(froot[i - 1], 0, maxx, 0, x1, 0, y1);
      froot[i] = update(froot[i], 0, maxx, x1 + 1, x2, a, b);
      froot[i] = update(froot[i], 0, maxx, x2 + 1, maxx, 0, y2);
    }
    int m;
    cin >> m;
    long long last = 0;
    while (m--) {
      int l, r, x;
      cin >> l >> r >> x;
      last = (last + x) % 1000000000ll;
      last =
          query(froot[r], 0, maxx, last) - query(froot[l - 1], 0, maxx, last);
      cout << last << endl;
    }
  }
  return 0;
}

```