#include <bits/stdc++.h>
using namespace std;
struct node {
  int lo, hi;
  long long sum;
  node *left, *right;
  node(int l, int h, long long s = 0)
      : lo(l), hi(h), sum(s), left(NULL), right(NULL){};
};
node *seg[75005];
node *seg2[75005];
void build(node *cur) {
  if (cur->lo == cur->hi) {
    return;
  }
  int mid = (cur->lo + cur->hi) / 2;
  cur->left = new node(cur->lo, mid);
  cur->right = new node(mid + 1, cur->hi);
  build(cur->left);
  build(cur->right);
  cur->sum = cur->left->sum + cur->right->sum;
}
void add(node *cur, node *par, int id, long long val) {
  if (cur->lo == cur->hi) {
    cur->sum = par->sum + val;
    return;
  }
  int mid = (cur->lo + cur->hi) / 2;
  if (mid >= id) {
    cur->left = new node(cur->lo, mid);
    cur->right = par->right;
    add(cur->left, par->left, id, val);
  } else {
    cur->left = par->left;
    cur->right = new node(mid + 1, cur->hi);
    add(cur->right, par->right, id, val);
  }
  cur->sum = cur->left->sum + cur->right->sum;
}
void update(int id, long long a, long long b, long long c, long long d,
            long long e, long long f) {
  node *temp;
  seg[id] = new node(0, 200005);
  add(seg[id], seg[id - 1], 1, c);
  temp = new node(0, 200005);
  add(temp, seg[id], a + 1, e - c);
  seg[id] = temp;
  temp = new node(0, 200005);
  add(temp, seg[id], b + 1, f - e);
  seg[id] = temp;
  seg2[id] = new node(0, 200005);
  add(seg2[id], seg2[id - 1], a + 1, d);
  temp = new node(0, 200005);
  add(temp, seg2[id], b + 1, -d);
  seg2[id] = temp;
}
long long getsum(node *cur, int lo, int hi) {
  if (cur->lo > hi || cur->hi < lo) {
    return 0;
  }
  if (lo <= cur->lo && cur->hi <= hi) {
    return cur->sum;
  }
  return getsum(cur->left, lo, hi) + getsum(cur->right, lo, hi);
}
long long query(long long a, long long b, long long c) {
  long long d = min(c, 200003LL);
  return getsum(seg[b], 1, d) - getsum(seg[a - 1], 1, d) +
         (getsum(seg2[b], 1, d) - getsum(seg2[a - 1], 1, d)) * c;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, i;
  long long a, b, c, d, e, f, ans = 0;
  cin >> n;
  seg[0] = new node(0, 200005);
  seg2[0] = new node(0, 200005);
  build(seg[0]);
  build(seg2[0]);
  for (i = 1; i <= n; ++i) {
    cin >> a >> b >> c >> d >> e >> f;
    update(i, a, b, c, d, e, f);
  }
  cin >> m;
  for (i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    c = (c + ans) % 1000000000;
    cout << (ans = query(a, b, c)) << "\n";
  }
  return 0;
}

### 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;
struct node {
  int lo, hi;
  long long sum;
  node *left, *right;
  node(int l, int h, long long s = 0)
      : lo(l), hi(h), sum(s), left(NULL), right(NULL){};
};
node *seg[75005];
node *seg2[75005];
void build(node *cur) {
  if (cur->lo == cur->hi) {
    return;
  }
  int mid = (cur->lo + cur->hi) / 2;
  cur->left = new node(cur->lo, mid);
  cur->right = new node(mid + 1, cur->hi);
  build(cur->left);
  build(cur->right);
  cur->sum = cur->left->sum + cur->right->sum;
}
void add(node *cur, node *par, int id, long long val) {
  if (cur->lo == cur->hi) {
    cur->sum = par->sum + val;
    return;
  }
  int mid = (cur->lo + cur->hi) / 2;
  if (mid >= id) {
    cur->left = new node(cur->lo, mid);
    cur->right = par->right;
    add(cur->left, par->left, id, val);
  } else {
    cur->left = par->left;
    cur->right = new node(mid + 1, cur->hi);
    add(cur->right, par->right, id, val);
  }
  cur->sum = cur->left->sum + cur->right->sum;
}
void update(int id, long long a, long long b, long long c, long long d,
            long long e, long long f) {
  node *temp;
  seg[id] = new node(0, 200005);
  add(seg[id], seg[id - 1], 1, c);
  temp = new node(0, 200005);
  add(temp, seg[id], a + 1, e - c);
  seg[id] = temp;
  temp = new node(0, 200005);
  add(temp, seg[id], b + 1, f - e);
  seg[id] = temp;
  seg2[id] = new node(0, 200005);
  add(seg2[id], seg2[id - 1], a + 1, d);
  temp = new node(0, 200005);
  add(temp, seg2[id], b + 1, -d);
  seg2[id] = temp;
}
long long getsum(node *cur, int lo, int hi) {
  if (cur->lo > hi || cur->hi < lo) {
    return 0;
  }
  if (lo <= cur->lo && cur->hi <= hi) {
    return cur->sum;
  }
  return getsum(cur->left, lo, hi) + getsum(cur->right, lo, hi);
}
long long query(long long a, long long b, long long c) {
  long long d = min(c, 200003LL);
  return getsum(seg[b], 1, d) - getsum(seg[a - 1], 1, d) +
         (getsum(seg2[b], 1, d) - getsum(seg2[a - 1], 1, d)) * c;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m, i;
  long long a, b, c, d, e, f, ans = 0;
  cin >> n;
  seg[0] = new node(0, 200005);
  seg2[0] = new node(0, 200005);
  build(seg[0]);
  build(seg2[0]);
  for (i = 1; i <= n; ++i) {
    cin >> a >> b >> c >> d >> e >> f;
    update(i, a, b, c, d, e, f);
  }
  cin >> m;
  for (i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    c = (c + ans) % 1000000000;
    cout << (ans = query(a, b, c)) << "\n";
  }
  return 0;
}

```