#include <bits/stdc++.h>
using namespace std;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
struct F {
  long long x1, x2, y1, y2, a, b;
};
struct UKU {
  vector<F> fs;
  vint ps;
  vint accA, accB;
  void add(F f) { fs.push_back(f); }
  inline long long idx(long long x) {
    return upper_bound((ps).begin(), (ps).end(), x) - ps.begin() - 1;
  }
  void build() {
    for (auto& f : fs) {
      ps.push_back(f.x1);
      ps.push_back(f.x2);
    }
    ps.push_back(0);
    ps.push_back(1000000000);
    sort((ps).begin(), (ps).end());
    ps.erase(unique((ps).begin(), (ps).end()), ps.end());
    accA.resize(ps.size());
    accB.resize(ps.size());
    for (auto& f : fs) {
      f.x1 = idx(f.x1);
      f.x2 = idx(f.x2);
      accB[0] += f.y1;
      accB[f.x1] -= f.y1;
      accA[f.x1] += f.a;
      accB[f.x1] += f.b;
      accA[f.x2] -= f.a;
      accB[f.x2] -= f.b;
      accB[f.x2] += f.y2;
    }
    for (long long i = 0; i + 1 < ps.size(); i++) {
      accA[i + 1] += accA[i];
      accB[i + 1] += accB[i];
    }
  }
  long long calc(long long x) {
    long long k = idx(x);
    long long a = accA[k];
    long long b = accB[k];
    return a * x + b;
  }
};
struct segtree {
  static const long long SEG = 1 << 17;
  vector<UKU> dat;
  segtree() : dat(SEG * 2) {}
  void add(long long k, F f) {
    k += SEG - 1;
    while (true) {
      dat[k].add(f);
      if (k == 0) break;
      k = (k - 1) / 2;
    }
  }
  void build(long long k = 0, long long l = 0, long long r = SEG) {
    dat[k].build();
    if (l + 1 == r) return;
    build(k * 2 + 1, l, (l + r) / 2);
    build(k * 2 + 2, (l + r) / 2, r);
  }
  long long query(long long a, long long b, long long x, long long k = 0,
                  long long l = 0, long long r = SEG) {
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) {
      return dat[k].calc(x);
    }
    return query(a, b, x, k * 2 + 1, l, (l + r) / 2) +
           query(a, b, x, k * 2 + 2, (l + r) / 2, r);
  }
};
long long N;
F fs[111111];
signed main() {
  scanf("%lld", &N);
  for (long long i = 0; i < (N); i++) {
    long long x1, x2, y1, y2, a, b;
    scanf("%lld%lld%lld%lld%lld%lld", &x1, &x2, &y1, &a, &b, &y2);
    x1++;
    x2++;
    fs[i] = {x1, x2, y1, y2, a, b};
  }
  segtree seg;
  for (long long i = 0; i < (N); i++) seg.add(i, fs[i]);
  seg.build();
  long long last = 0;
  long long Q;
  scanf("%lld", &Q);
  while (Q--) {
    long long l, r, x;
    scanf("%lld%lld%lld", &l, &r, &x);
    l--;
    x = (x + last) % 1000000000;
    last = seg.query(l, r, x);
    printf("%lld\n", last);
  }
  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;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
struct F {
  long long x1, x2, y1, y2, a, b;
};
struct UKU {
  vector<F> fs;
  vint ps;
  vint accA, accB;
  void add(F f) { fs.push_back(f); }
  inline long long idx(long long x) {
    return upper_bound((ps).begin(), (ps).end(), x) - ps.begin() - 1;
  }
  void build() {
    for (auto& f : fs) {
      ps.push_back(f.x1);
      ps.push_back(f.x2);
    }
    ps.push_back(0);
    ps.push_back(1000000000);
    sort((ps).begin(), (ps).end());
    ps.erase(unique((ps).begin(), (ps).end()), ps.end());
    accA.resize(ps.size());
    accB.resize(ps.size());
    for (auto& f : fs) {
      f.x1 = idx(f.x1);
      f.x2 = idx(f.x2);
      accB[0] += f.y1;
      accB[f.x1] -= f.y1;
      accA[f.x1] += f.a;
      accB[f.x1] += f.b;
      accA[f.x2] -= f.a;
      accB[f.x2] -= f.b;
      accB[f.x2] += f.y2;
    }
    for (long long i = 0; i + 1 < ps.size(); i++) {
      accA[i + 1] += accA[i];
      accB[i + 1] += accB[i];
    }
  }
  long long calc(long long x) {
    long long k = idx(x);
    long long a = accA[k];
    long long b = accB[k];
    return a * x + b;
  }
};
struct segtree {
  static const long long SEG = 1 << 17;
  vector<UKU> dat;
  segtree() : dat(SEG * 2) {}
  void add(long long k, F f) {
    k += SEG - 1;
    while (true) {
      dat[k].add(f);
      if (k == 0) break;
      k = (k - 1) / 2;
    }
  }
  void build(long long k = 0, long long l = 0, long long r = SEG) {
    dat[k].build();
    if (l + 1 == r) return;
    build(k * 2 + 1, l, (l + r) / 2);
    build(k * 2 + 2, (l + r) / 2, r);
  }
  long long query(long long a, long long b, long long x, long long k = 0,
                  long long l = 0, long long r = SEG) {
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) {
      return dat[k].calc(x);
    }
    return query(a, b, x, k * 2 + 1, l, (l + r) / 2) +
           query(a, b, x, k * 2 + 2, (l + r) / 2, r);
  }
};
long long N;
F fs[111111];
signed main() {
  scanf("%lld", &N);
  for (long long i = 0; i < (N); i++) {
    long long x1, x2, y1, y2, a, b;
    scanf("%lld%lld%lld%lld%lld%lld", &x1, &x2, &y1, &a, &b, &y2);
    x1++;
    x2++;
    fs[i] = {x1, x2, y1, y2, a, b};
  }
  segtree seg;
  for (long long i = 0; i < (N); i++) seg.add(i, fs[i]);
  seg.build();
  long long last = 0;
  long long Q;
  scanf("%lld", &Q);
  while (Q--) {
    long long l, r, x;
    scanf("%lld%lld%lld", &l, &r, &x);
    l--;
    x = (x + last) % 1000000000;
    last = seg.query(l, r, x);
    printf("%lld\n", last);
  }
  return 0;
}

```