#include <bits/stdc++.h>
using namespace std;
inline int getidx(const vector<int> &ar, int x) {
  return lower_bound(ar.begin(), ar.end(), x) - ar.begin();
}
inline long long GCD(long long a, long long b) {
  long long n;
  if (a < b) swap(a, b);
  while (b != 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}
inline long long LCM(long long a, long long b) {
  if (a == 0 || b == 0) return GCD(a, b);
  return a / GCD(a, b) * b;
}
inline long long CEIL(long long n, long long d) {
  return n / d + (long long)(n % d != 0);
}
inline long long ROUND(long long n, long long d) {
  return n / d + (long long)((n % d) * 2 >= d);
}
inline long long POW(long long a, long long n) {
  if (n < 0) return 0;
  long long ret = 1;
  while (n) {
    if (n % 2) ret *= a;
    a = a * a;
    n /= 2;
  }
  return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const int MAXN = 75000 + 10, RANGE = 2e5 + 10, MOD = 1e9;
struct node {
  long long x;
  node *l, *r;
  node(long long x = 0, node *l = 0, node *r = 0) : x(x), l(l), r(r) {}
  node *addtree(int u, long long c, int ns = 0, int ne = RANGE) {
    if (ns <= u && u <= ne) {
      if (ns == ne) return new node(x + c);
      int mid = (ns + ne) / 2;
      return new node(x + c, l->addtree(u, c, ns, mid),
                      r->addtree(u, c, mid + 1, ne));
    }
    return this;
  }
  long long sum(int s, int e, int ns = 0, int ne = RANGE) {
    if (s <= ns && ne <= e) return x;
    if (e < ns || ne < s) return 0;
    int mid = (ns + ne) / 2;
    return l->sum(s, e, ns, mid) + r->sum(s, e, mid + 1, ne);
  }
} * coe[MAXN], *cons[MAXN], *nul;
int n, m;
void input() {
  cin >> n;
  nul = new node();
  nul->l = nul->r = nul;
  coe[0] = cons[0] = nul;
  for (int(i) = (1); (i) < (int)(n + 1); ++(i)) {
    int sx, ex, v1, v2, av, bv;
    cin >> sx >> ex >> v1 >> av >> bv >> v2;
    coe[i] = coe[i - 1];
    cons[i] = cons[i - 1];
    coe[i] = coe[i]->addtree(sx + 1, av);
    coe[i] = coe[i]->addtree(ex + 1, -av);
    cons[i] = cons[i]->addtree(0, v1);
    cons[i] = cons[i]->addtree(sx + 1, bv - v1);
    cons[i] = cons[i]->addtree(ex + 1, v2 - bv);
  }
  cin >> m;
}
int solve() {
  long long res = 0;
  while (m--) {
    long long l, r, x;
    cin >> l >> r >> x;
    x = (x + (res % MOD)) % MOD;
    42;
    res = x * (coe[r]->sum(0, x) - coe[l - 1]->sum(0, x)) + cons[r]->sum(0, x) -
          cons[l - 1]->sum(0, x);
    cout << res << '\n';
  }
  return 0;
}
void execute() { input(), solve(); }
int main(void) {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  execute();
  return 0;
}

### Prompt

Your challenge is to write 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;
inline int getidx(const vector<int> &ar, int x) {
  return lower_bound(ar.begin(), ar.end(), x) - ar.begin();
}
inline long long GCD(long long a, long long b) {
  long long n;
  if (a < b) swap(a, b);
  while (b != 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}
inline long long LCM(long long a, long long b) {
  if (a == 0 || b == 0) return GCD(a, b);
  return a / GCD(a, b) * b;
}
inline long long CEIL(long long n, long long d) {
  return n / d + (long long)(n % d != 0);
}
inline long long ROUND(long long n, long long d) {
  return n / d + (long long)((n % d) * 2 >= d);
}
inline long long POW(long long a, long long n) {
  if (n < 0) return 0;
  long long ret = 1;
  while (n) {
    if (n % 2) ret *= a;
    a = a * a;
    n /= 2;
  }
  return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const int MAXN = 75000 + 10, RANGE = 2e5 + 10, MOD = 1e9;
struct node {
  long long x;
  node *l, *r;
  node(long long x = 0, node *l = 0, node *r = 0) : x(x), l(l), r(r) {}
  node *addtree(int u, long long c, int ns = 0, int ne = RANGE) {
    if (ns <= u && u <= ne) {
      if (ns == ne) return new node(x + c);
      int mid = (ns + ne) / 2;
      return new node(x + c, l->addtree(u, c, ns, mid),
                      r->addtree(u, c, mid + 1, ne));
    }
    return this;
  }
  long long sum(int s, int e, int ns = 0, int ne = RANGE) {
    if (s <= ns && ne <= e) return x;
    if (e < ns || ne < s) return 0;
    int mid = (ns + ne) / 2;
    return l->sum(s, e, ns, mid) + r->sum(s, e, mid + 1, ne);
  }
} * coe[MAXN], *cons[MAXN], *nul;
int n, m;
void input() {
  cin >> n;
  nul = new node();
  nul->l = nul->r = nul;
  coe[0] = cons[0] = nul;
  for (int(i) = (1); (i) < (int)(n + 1); ++(i)) {
    int sx, ex, v1, v2, av, bv;
    cin >> sx >> ex >> v1 >> av >> bv >> v2;
    coe[i] = coe[i - 1];
    cons[i] = cons[i - 1];
    coe[i] = coe[i]->addtree(sx + 1, av);
    coe[i] = coe[i]->addtree(ex + 1, -av);
    cons[i] = cons[i]->addtree(0, v1);
    cons[i] = cons[i]->addtree(sx + 1, bv - v1);
    cons[i] = cons[i]->addtree(ex + 1, v2 - bv);
  }
  cin >> m;
}
int solve() {
  long long res = 0;
  while (m--) {
    long long l, r, x;
    cin >> l >> r >> x;
    x = (x + (res % MOD)) % MOD;
    42;
    res = x * (coe[r]->sum(0, x) - coe[l - 1]->sum(0, x)) + cons[r]->sum(0, x) -
          cons[l - 1]->sum(0, x);
    cout << res << '\n';
  }
  return 0;
}
void execute() { input(), solve(); }
int main(void) {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  execute();
  return 0;
}

```