#include <bits/stdc++.h>
using namespace std;
struct line {
  long long k, b;
  line() {}
  line(long long k, long long b) : k(k), b(b) {}
  bool zero() const { return k == 0 && b == 0; }
};
line operator+(const line &a, const line &b) {
  return line(a.k + b.k, a.b + b.b);
}
line operator-(const line &a, const line &b) {
  return line(a.k - b.k, a.b - b.b);
}
struct node {
  line sum, lazy;
  node *L, *R;
  node() {}
  node(line sum, line lazy, node *L, node *R)
      : sum(sum), lazy(lazy), L(L), R(R) {}
  node *copy() { return new node(sum, lazy, L, R); }
  node *work(line x) { return new node(sum + x, lazy + x, L, R); }
};
node *build(int l, int r) {
  if (l == r) return new node(line(0, 0), line(0, 0), NULL, NULL);
  int mid = (l + r) / 2;
  return new node(line(0, 0), line(0, 0), build(l, mid), build(mid + 1, r));
}
const int N = 75005;
node *tree[N];
vector<int> ax;
void add(node *&x, int l, int r, int ql, int qr, line c) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    x = x->work(c);
    return;
  }
  int mid = (l + r) / 2;
  x = x->copy();
  add(x->L, l, mid, ql, qr, c);
  add(x->R, mid + 1, r, ql, qr, c);
}
line query(node *x, int l, int r, int q) {
  if (l > q || r < q) return line(0, 0);
  if (l == r) return x->sum;
  int mid = (l + r) / 2;
  return x->sum + query(x->L, l, mid, q) + query(x->R, mid + 1, r, q);
}
int getx(int x) {
  return upper_bound(ax.begin(), ax.end(), x) - ax.begin() - 1;
}
int x1[N], x2[N], adsf[N], y2[N], a[N], b[N];
int main() {
  int n;
  scanf("%d", &n);
  ax.push_back(0);
  ax.push_back(1e9);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d%d%d%d", &x1[i], &x2[i], &adsf[i], &a[i], &b[i], &y2[i]);
    ax.push_back(x1[i] + 1);
    ax.push_back(x2[i] + 1);
  }
  sort(ax.begin(), ax.end());
  ax.erase(unique(ax.begin(), ax.end()), ax.end());
  tree[0] = build(0, ax.size() - 1);
  for (int i = 1; i <= n; ++i) {
    tree[i] = tree[i - 1];
    int x1 = getx(::x1[i] + 1);
    int x2 = getx(::x2[i] + 1);
    add(tree[i], 0, ax.size() - 1, 0, x1 - 1, line(0, adsf[i]));
    add(tree[i], 0, ax.size() - 1, x1, x2 - 1, line(a[i], b[i]));
    add(tree[i], 0, ax.size() - 1, x2, ax.size() - 1, line(0, y2[i]));
  }
  int m;
  long long las = 0;
  scanf("%d", &m);
  while (m--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x = (las + x) % (int)1e9;
    line res = query(tree[r], 0, ax.size() - 1, getx(x)) -
               query(tree[l - 1], 0, ax.size() - 1, getx(x));
    las = res.k * x + res.b;
    printf("%I64d\n", las);
  }
}

### 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 line {
  long long k, b;
  line() {}
  line(long long k, long long b) : k(k), b(b) {}
  bool zero() const { return k == 0 && b == 0; }
};
line operator+(const line &a, const line &b) {
  return line(a.k + b.k, a.b + b.b);
}
line operator-(const line &a, const line &b) {
  return line(a.k - b.k, a.b - b.b);
}
struct node {
  line sum, lazy;
  node *L, *R;
  node() {}
  node(line sum, line lazy, node *L, node *R)
      : sum(sum), lazy(lazy), L(L), R(R) {}
  node *copy() { return new node(sum, lazy, L, R); }
  node *work(line x) { return new node(sum + x, lazy + x, L, R); }
};
node *build(int l, int r) {
  if (l == r) return new node(line(0, 0), line(0, 0), NULL, NULL);
  int mid = (l + r) / 2;
  return new node(line(0, 0), line(0, 0), build(l, mid), build(mid + 1, r));
}
const int N = 75005;
node *tree[N];
vector<int> ax;
void add(node *&x, int l, int r, int ql, int qr, line c) {
  if (l > qr || r < ql) return;
  if (l >= ql && r <= qr) {
    x = x->work(c);
    return;
  }
  int mid = (l + r) / 2;
  x = x->copy();
  add(x->L, l, mid, ql, qr, c);
  add(x->R, mid + 1, r, ql, qr, c);
}
line query(node *x, int l, int r, int q) {
  if (l > q || r < q) return line(0, 0);
  if (l == r) return x->sum;
  int mid = (l + r) / 2;
  return x->sum + query(x->L, l, mid, q) + query(x->R, mid + 1, r, q);
}
int getx(int x) {
  return upper_bound(ax.begin(), ax.end(), x) - ax.begin() - 1;
}
int x1[N], x2[N], adsf[N], y2[N], a[N], b[N];
int main() {
  int n;
  scanf("%d", &n);
  ax.push_back(0);
  ax.push_back(1e9);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d%d%d%d", &x1[i], &x2[i], &adsf[i], &a[i], &b[i], &y2[i]);
    ax.push_back(x1[i] + 1);
    ax.push_back(x2[i] + 1);
  }
  sort(ax.begin(), ax.end());
  ax.erase(unique(ax.begin(), ax.end()), ax.end());
  tree[0] = build(0, ax.size() - 1);
  for (int i = 1; i <= n; ++i) {
    tree[i] = tree[i - 1];
    int x1 = getx(::x1[i] + 1);
    int x2 = getx(::x2[i] + 1);
    add(tree[i], 0, ax.size() - 1, 0, x1 - 1, line(0, adsf[i]));
    add(tree[i], 0, ax.size() - 1, x1, x2 - 1, line(a[i], b[i]));
    add(tree[i], 0, ax.size() - 1, x2, ax.size() - 1, line(0, y2[i]));
  }
  int m;
  long long las = 0;
  scanf("%d", &m);
  while (m--) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x = (las + x) % (int)1e9;
    line res = query(tree[r], 0, ax.size() - 1, getx(x)) -
               query(tree[l - 1], 0, ax.size() - 1, getx(x));
    las = res.k * x + res.b;
    printf("%I64d\n", las);
  }
}

```