#include <bits/stdc++.h>
using namespace std;
const int neutral = 0;
const int n = 200002;
int NEXT_FREE_INDEX = 1, ir = 0;
struct node {
  long long a, b;
  node(long long a, long long b) : a(a), b(b) {}
  node() : a(0), b(0) {}
};
int L[4950005], R[4950005], root[75005 + 5];
node s[4950005], a[n + 5];
node add(node a, node b) { return node(a.a + b.a, a.b + b.b); }
void build(int id = ir, int l = 0, int r = n) {
  if (r - l < 2) {
    s[id] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  L[id] = NEXT_FREE_INDEX++;
  R[id] = NEXT_FREE_INDEX++;
  build(L[id], l, mid);
  build(R[id], mid, r);
  s[id] = add(s[L[id]], s[R[id]]);
}
int upd(int p, node v, int id, int l = 0, int r = n) {
  int ID = NEXT_FREE_INDEX++;
  if (r - l < 2) {
    a[p] = add(a[p], v);
    s[ID] = a[p];
    return ID;
  }
  int mid = (l + r) / 2;
  L[ID] = L[id], R[ID] = R[id];
  if (p < mid)
    L[ID] = upd(p, v, L[ID], l, mid);
  else
    R[ID] = upd(p, v, R[ID], mid, r);
  s[ID] = add(s[L[ID]], s[R[ID]]);
  return ID;
}
node query(int x, int y, int id, int l = 0, int r = n) {
  if (x >= r or l >= y) return node(0, 0);
  if (x <= l && r <= y) return s[id];
  int mid = (l + r) / 2;
  return add(query(x, y, L[id], l, mid), query(x, y, R[id], mid, r));
}
int vet[16];
int main() {
  int retas;
  scanf("%d", &retas);
  for (int i = 0; i < retas; i++) {
    int x1, x2, y1, a, b, y2, p;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    int prev = (i == 0) ? ir : root[i - 1];
    root[i] = upd(0, node(0, y1), prev);
    root[i] = upd(x1, node(a, -y1 + b), root[i]);
    root[i] = upd(x2, node(-a, y2 - b), root[i]);
  }
  int m, ult = 0;
  scanf("%d", &m);
  while (m--) {
    int x, l, r;
    scanf("%d %d %d", &l, &r, &x);
    x = (x + ult) % 1000000000;
    node tmp1 = (l == 1) ? node(0, 0) : query(0, min(x, n), root[l - 2]);
    node tmp2 = query(0, min(x, n), root[r - 1]);
    printf("%I64d\n", (tmp2.a - tmp1.a) * x + (tmp2.b - tmp1.b));
    ult = ((tmp2.a - tmp1.a) * x + (tmp2.b - tmp1.b)) % 1000000000;
  }
  return 0;
}

### Prompt

Please formulate 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;
const int neutral = 0;
const int n = 200002;
int NEXT_FREE_INDEX = 1, ir = 0;
struct node {
  long long a, b;
  node(long long a, long long b) : a(a), b(b) {}
  node() : a(0), b(0) {}
};
int L[4950005], R[4950005], root[75005 + 5];
node s[4950005], a[n + 5];
node add(node a, node b) { return node(a.a + b.a, a.b + b.b); }
void build(int id = ir, int l = 0, int r = n) {
  if (r - l < 2) {
    s[id] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  L[id] = NEXT_FREE_INDEX++;
  R[id] = NEXT_FREE_INDEX++;
  build(L[id], l, mid);
  build(R[id], mid, r);
  s[id] = add(s[L[id]], s[R[id]]);
}
int upd(int p, node v, int id, int l = 0, int r = n) {
  int ID = NEXT_FREE_INDEX++;
  if (r - l < 2) {
    a[p] = add(a[p], v);
    s[ID] = a[p];
    return ID;
  }
  int mid = (l + r) / 2;
  L[ID] = L[id], R[ID] = R[id];
  if (p < mid)
    L[ID] = upd(p, v, L[ID], l, mid);
  else
    R[ID] = upd(p, v, R[ID], mid, r);
  s[ID] = add(s[L[ID]], s[R[ID]]);
  return ID;
}
node query(int x, int y, int id, int l = 0, int r = n) {
  if (x >= r or l >= y) return node(0, 0);
  if (x <= l && r <= y) return s[id];
  int mid = (l + r) / 2;
  return add(query(x, y, L[id], l, mid), query(x, y, R[id], mid, r));
}
int vet[16];
int main() {
  int retas;
  scanf("%d", &retas);
  for (int i = 0; i < retas; i++) {
    int x1, x2, y1, a, b, y2, p;
    scanf("%d %d %d %d %d %d", &x1, &x2, &y1, &a, &b, &y2);
    int prev = (i == 0) ? ir : root[i - 1];
    root[i] = upd(0, node(0, y1), prev);
    root[i] = upd(x1, node(a, -y1 + b), root[i]);
    root[i] = upd(x2, node(-a, y2 - b), root[i]);
  }
  int m, ult = 0;
  scanf("%d", &m);
  while (m--) {
    int x, l, r;
    scanf("%d %d %d", &l, &r, &x);
    x = (x + ult) % 1000000000;
    node tmp1 = (l == 1) ? node(0, 0) : query(0, min(x, n), root[l - 2]);
    node tmp2 = query(0, min(x, n), root[r - 1]);
    printf("%I64d\n", (tmp2.a - tmp1.a) * x + (tmp2.b - tmp1.b));
    ult = ((tmp2.a - tmp1.a) * x + (tmp2.b - tmp1.b)) % 1000000000;
  }
  return 0;
}

```