#include <bits/stdc++.h>
using namespace std;
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
void file() {}
void fast() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
}
struct node;
extern node* emptyNode;
struct node {
  long long a, b;
  node *l, *r;
  node() {
    a = b = 0;
    l = r = this;
  }
  node(long long a, long long b, node* l = emptyNode, node* r = emptyNode) {
    this->a = a, this->b = b;
    this->l = l, this->r = r;
  }
};
node* emptyNode = new node();
node* insert(node* root, int startNode, int endNode, int qV,
             pair<int, int> val) {
  if (qV < startNode || qV > endNode) return root;
  if (startNode == endNode)
    return new node(root->a + val.first, root->b + val.second);
  int mid = startNode + (endNode - startNode) / 2;
  node* insertL = insert(root->l, startNode, mid, qV, val);
  node* insertR = insert(root->r, mid + 1, endNode, qV, val);
  return new node(insertL->a + insertR->a, insertL->b + insertR->b, insertL,
                  insertR);
}
pair<long long, long long> query(node* root, int startNode, int endNode, int qS,
                                 int qE) {
  if (qE < startNode || qS > endNode) return {0, 0};
  if (qS <= startNode && qE >= endNode) return {root->a, root->b};
  int mid = startNode + (endNode - startNode) / 2;
  auto l = query(root->l, startNode, mid, qS, qE);
  auto r = query(root->r, mid + 1, endNode, qS, qE);
  return {l.first + r.first, l.second + r.second};
}
const int N = 75000 + 9;
node *X1Min[N], *X1[N], *X2Y[N], *X2[N];
const int L = -1, R = 2e5 + 1;
long long solve(int i, int x) {
  long long ret = query(X1Min[i], L, R, x, R).first;
  ret += query(X2Y[i], L, R, L, x - 1).first;
  auto gt = query(X1[i], L, R, L, x - 1);
  ret += gt.first * x;
  ret += gt.second;
  gt = query(X2[i], L, R, L, x - 1);
  ret -= (gt.first * x + gt.second);
  return ret;
}
int main() {
  file();
  X1Min[0] = X1[0] = X2Y[0] = X2[0] = emptyNode;
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x1, x2, y1, a, b, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    X1Min[i] = insert(X1Min[i - 1], L, R, x1, {y1, 0});
    X1[i] = insert(X1[i - 1], L, R, x1, {a, b});
    X2Y[i] = insert(X2Y[i - 1], L, R, x2, {y2, 0});
    X2[i] = insert(X2[i - 1], L, R, x2, {a, b});
  }
  int m;
  cin >> m;
  long long last = 0;
  while (m--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    x = (x + last) % (int)1e9;
    last = solve(r, x) - solve(l - 1, x);
    cout << last << "\n";
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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;
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
void file() {}
void fast() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
}
struct node;
extern node* emptyNode;
struct node {
  long long a, b;
  node *l, *r;
  node() {
    a = b = 0;
    l = r = this;
  }
  node(long long a, long long b, node* l = emptyNode, node* r = emptyNode) {
    this->a = a, this->b = b;
    this->l = l, this->r = r;
  }
};
node* emptyNode = new node();
node* insert(node* root, int startNode, int endNode, int qV,
             pair<int, int> val) {
  if (qV < startNode || qV > endNode) return root;
  if (startNode == endNode)
    return new node(root->a + val.first, root->b + val.second);
  int mid = startNode + (endNode - startNode) / 2;
  node* insertL = insert(root->l, startNode, mid, qV, val);
  node* insertR = insert(root->r, mid + 1, endNode, qV, val);
  return new node(insertL->a + insertR->a, insertL->b + insertR->b, insertL,
                  insertR);
}
pair<long long, long long> query(node* root, int startNode, int endNode, int qS,
                                 int qE) {
  if (qE < startNode || qS > endNode) return {0, 0};
  if (qS <= startNode && qE >= endNode) return {root->a, root->b};
  int mid = startNode + (endNode - startNode) / 2;
  auto l = query(root->l, startNode, mid, qS, qE);
  auto r = query(root->r, mid + 1, endNode, qS, qE);
  return {l.first + r.first, l.second + r.second};
}
const int N = 75000 + 9;
node *X1Min[N], *X1[N], *X2Y[N], *X2[N];
const int L = -1, R = 2e5 + 1;
long long solve(int i, int x) {
  long long ret = query(X1Min[i], L, R, x, R).first;
  ret += query(X2Y[i], L, R, L, x - 1).first;
  auto gt = query(X1[i], L, R, L, x - 1);
  ret += gt.first * x;
  ret += gt.second;
  gt = query(X2[i], L, R, L, x - 1);
  ret -= (gt.first * x + gt.second);
  return ret;
}
int main() {
  file();
  X1Min[0] = X1[0] = X2Y[0] = X2[0] = emptyNode;
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x1, x2, y1, a, b, y2;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    X1Min[i] = insert(X1Min[i - 1], L, R, x1, {y1, 0});
    X1[i] = insert(X1[i - 1], L, R, x1, {a, b});
    X2Y[i] = insert(X2Y[i - 1], L, R, x2, {y2, 0});
    X2[i] = insert(X2[i - 1], L, R, x2, {a, b});
  }
  int m;
  cin >> m;
  long long last = 0;
  while (m--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    x = (x + last) % (int)1e9;
    last = solve(r, x) - solve(l - 1, x);
    cout << last << "\n";
  }
  return 0;
}

```