#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 75000 + 10;
int qX1[MAX_N], qX2[MAX_N], qY1[MAX_N], qA[MAX_N], qB[MAX_N], qY2[MAX_N];
bool cmpX1(int i, int j) {
  if (qX1[i] < qX1[j]) {
    return 1;
  }
  if (qX1[i] > qX1[j]) {
    return 0;
  }
  if (qX1[i] == qX1[j]) {
    return i < j;
  }
}
bool cmpX2(int i, int j) {
  if (qX2[i] < qX2[j]) {
    return 1;
  }
  if (qX2[i] > qX2[j]) {
    return 0;
  }
  if (qX2[i] == qX2[j]) {
    return i < j;
  }
}
class Node {
 public:
  int l, r;
  Node *leftChild, *rightChild, *parent;
  vector<int> X1, X2;
  vector<long long> sumAX2, sumBX2, sumAX1, sumBX1, sumY1, sumY2;
  Node(int l, int r, Node *parent) {
    this->l = l;
    this->r = r;
    leftChild = NULL;
    rightChild = NULL;
    this->parent = parent;
    init();
    build();
  }
  void init() {
    X1.clear();
    X2.clear();
    sumAX1.clear();
    sumBX1.clear();
    sumAX2.clear();
    sumBX2.clear();
    sumY1.clear();
    sumY2.clear();
  }
  void build() {
    if (l == r) {
      return;
    }
    int mid = (l + r) / 2;
    leftChild = new Node(l, mid, this);
    rightChild = new Node(mid + 1, r, this);
  }
  void update(int index) {
    if (index < l || index > r) {
      return;
    }
    X1.push_back(index);
    X2.push_back(index);
    if (leftChild != NULL) {
      leftChild->update(index);
    }
    if (rightChild != NULL) {
      rightChild->update(index);
    }
  }
  void relax() {
    sort(X1.begin(), X1.end(), cmpX1);
    sort(X2.begin(), X2.end(), cmpX2);
    sumY1.push_back(qY1[X1[X1.size() - 1]]);
    sumAX1.push_back(qA[X1[X1.size() - 1]]);
    sumBX1.push_back(qB[X1[X1.size() - 1]]);
    for (int i = X1.size() - 2; i >= 0; i--) {
      sumY1.push_back(qY1[X1[i]] + sumY1[sumY1.size() - 1]);
      sumAX1.push_back(qA[X1[i]] + sumAX1[sumAX1.size() - 1]);
      sumBX1.push_back(qB[X1[i]] + sumBX1[sumBX1.size() - 1]);
    }
    reverse(sumY1.begin(), sumY1.end());
    reverse(sumAX1.begin(), sumAX1.end());
    reverse(sumBX1.begin(), sumBX1.end());
    sumY2.push_back(qY2[X2[0]]);
    sumAX2.push_back(qA[X2[0]]);
    sumBX2.push_back(qB[X2[0]]);
    for (int i = 1; i < X2.size(); i++) {
      sumY2.push_back(qY2[X2[i]] + sumY2[sumY2.size() - 1]);
      sumAX2.push_back(qA[X2[i]] + sumAX2[sumAX2.size() - 1]);
      sumBX2.push_back(qB[X2[i]] + sumBX2[sumBX2.size() - 1]);
    }
    if (leftChild != NULL) {
      leftChild->relax();
    }
    if (rightChild != NULL) {
      rightChild->relax();
    }
  }
  long long get(int L, int R, int X) {
    if (this->l > R || this->r < L) {
      return 0ll;
    }
    if (!(L <= this->l && this->r <= R)) {
      if (leftChild != NULL && rightChild != NULL) {
        return (leftChild->get(L, R, X) + rightChild->get(L, R, X));
      } else {
        return 0ll;
      }
    }
    long long ret = 0;
    long long totalA = sumAX1[0];
    long long totalB = sumBX1[0];
    {
      int first = 0;
      int last = X1.size() - 1;
      while (first < last) {
        int mid = (first + last) / 2;
        if (qX1[X1[mid]] < X) {
          first = mid + 1;
        } else {
          last = mid;
        }
      }
      ret += sumY1[last];
      totalA -= sumAX1[last];
      totalB -= sumBX1[last];
      if (qX1[X1[last]] < X) {
        ret -= qY1[X1[last]];
        totalA += qA[X1[last]];
        totalB += qB[X1[last]];
      }
    }
    {
      int first = 0;
      int last = X2.size() - 1;
      while (first < last) {
        int mid = (first + last) / 2;
        if (qX2[X2[mid]] < X) {
          first = mid + 1;
        } else {
          last = mid;
        }
      }
      ret += sumY2[last];
      totalA -= sumAX2[last];
      totalB -= sumBX2[last];
      if (qX2[X2[last]] >= X) {
        ret -= qY2[X2[last]];
        totalA += qA[X2[last]];
        totalB += qB[X2[last]];
      }
    }
    ret += (long long)((long long)totalA * (long long)X) + ((long long)totalB);
    return ret;
  }
};
class SegmentTree {
 public:
  Node *root;
  SegmentTree(int n) { root = new Node(1, n, NULL); }
  void update(int index) { root->update(index); }
  void relax() { root->relax(); }
  long long get(int l, int r, int x) { return root->get(l, r, x); }
};
int main() {
  int n;
  scanf("%d", &n);
  SegmentTree *st = new SegmentTree(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d%d%d%d", &qX1[i], &qX2[i], &qY1[i], &qA[i], &qB[i], &qY2[i]);
    st->update(i);
  }
  st->relax();
  int m;
  scanf("%d", &m);
  const long long mod = 1000000000;
  int past = 0;
  long long ans;
  for (int i = 1; i <= m; i++) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x = (((long long)past) + ((long long)x)) % mod;
    ans = st->get(l, r, x);
    past = ans % mod;
    printf("%lld\n", ans);
  }
}

### Prompt

Please create a solution in Cpp 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 MAX_N = 75000 + 10;
int qX1[MAX_N], qX2[MAX_N], qY1[MAX_N], qA[MAX_N], qB[MAX_N], qY2[MAX_N];
bool cmpX1(int i, int j) {
  if (qX1[i] < qX1[j]) {
    return 1;
  }
  if (qX1[i] > qX1[j]) {
    return 0;
  }
  if (qX1[i] == qX1[j]) {
    return i < j;
  }
}
bool cmpX2(int i, int j) {
  if (qX2[i] < qX2[j]) {
    return 1;
  }
  if (qX2[i] > qX2[j]) {
    return 0;
  }
  if (qX2[i] == qX2[j]) {
    return i < j;
  }
}
class Node {
 public:
  int l, r;
  Node *leftChild, *rightChild, *parent;
  vector<int> X1, X2;
  vector<long long> sumAX2, sumBX2, sumAX1, sumBX1, sumY1, sumY2;
  Node(int l, int r, Node *parent) {
    this->l = l;
    this->r = r;
    leftChild = NULL;
    rightChild = NULL;
    this->parent = parent;
    init();
    build();
  }
  void init() {
    X1.clear();
    X2.clear();
    sumAX1.clear();
    sumBX1.clear();
    sumAX2.clear();
    sumBX2.clear();
    sumY1.clear();
    sumY2.clear();
  }
  void build() {
    if (l == r) {
      return;
    }
    int mid = (l + r) / 2;
    leftChild = new Node(l, mid, this);
    rightChild = new Node(mid + 1, r, this);
  }
  void update(int index) {
    if (index < l || index > r) {
      return;
    }
    X1.push_back(index);
    X2.push_back(index);
    if (leftChild != NULL) {
      leftChild->update(index);
    }
    if (rightChild != NULL) {
      rightChild->update(index);
    }
  }
  void relax() {
    sort(X1.begin(), X1.end(), cmpX1);
    sort(X2.begin(), X2.end(), cmpX2);
    sumY1.push_back(qY1[X1[X1.size() - 1]]);
    sumAX1.push_back(qA[X1[X1.size() - 1]]);
    sumBX1.push_back(qB[X1[X1.size() - 1]]);
    for (int i = X1.size() - 2; i >= 0; i--) {
      sumY1.push_back(qY1[X1[i]] + sumY1[sumY1.size() - 1]);
      sumAX1.push_back(qA[X1[i]] + sumAX1[sumAX1.size() - 1]);
      sumBX1.push_back(qB[X1[i]] + sumBX1[sumBX1.size() - 1]);
    }
    reverse(sumY1.begin(), sumY1.end());
    reverse(sumAX1.begin(), sumAX1.end());
    reverse(sumBX1.begin(), sumBX1.end());
    sumY2.push_back(qY2[X2[0]]);
    sumAX2.push_back(qA[X2[0]]);
    sumBX2.push_back(qB[X2[0]]);
    for (int i = 1; i < X2.size(); i++) {
      sumY2.push_back(qY2[X2[i]] + sumY2[sumY2.size() - 1]);
      sumAX2.push_back(qA[X2[i]] + sumAX2[sumAX2.size() - 1]);
      sumBX2.push_back(qB[X2[i]] + sumBX2[sumBX2.size() - 1]);
    }
    if (leftChild != NULL) {
      leftChild->relax();
    }
    if (rightChild != NULL) {
      rightChild->relax();
    }
  }
  long long get(int L, int R, int X) {
    if (this->l > R || this->r < L) {
      return 0ll;
    }
    if (!(L <= this->l && this->r <= R)) {
      if (leftChild != NULL && rightChild != NULL) {
        return (leftChild->get(L, R, X) + rightChild->get(L, R, X));
      } else {
        return 0ll;
      }
    }
    long long ret = 0;
    long long totalA = sumAX1[0];
    long long totalB = sumBX1[0];
    {
      int first = 0;
      int last = X1.size() - 1;
      while (first < last) {
        int mid = (first + last) / 2;
        if (qX1[X1[mid]] < X) {
          first = mid + 1;
        } else {
          last = mid;
        }
      }
      ret += sumY1[last];
      totalA -= sumAX1[last];
      totalB -= sumBX1[last];
      if (qX1[X1[last]] < X) {
        ret -= qY1[X1[last]];
        totalA += qA[X1[last]];
        totalB += qB[X1[last]];
      }
    }
    {
      int first = 0;
      int last = X2.size() - 1;
      while (first < last) {
        int mid = (first + last) / 2;
        if (qX2[X2[mid]] < X) {
          first = mid + 1;
        } else {
          last = mid;
        }
      }
      ret += sumY2[last];
      totalA -= sumAX2[last];
      totalB -= sumBX2[last];
      if (qX2[X2[last]] >= X) {
        ret -= qY2[X2[last]];
        totalA += qA[X2[last]];
        totalB += qB[X2[last]];
      }
    }
    ret += (long long)((long long)totalA * (long long)X) + ((long long)totalB);
    return ret;
  }
};
class SegmentTree {
 public:
  Node *root;
  SegmentTree(int n) { root = new Node(1, n, NULL); }
  void update(int index) { root->update(index); }
  void relax() { root->relax(); }
  long long get(int l, int r, int x) { return root->get(l, r, x); }
};
int main() {
  int n;
  scanf("%d", &n);
  SegmentTree *st = new SegmentTree(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d%d%d%d", &qX1[i], &qX2[i], &qY1[i], &qA[i], &qB[i], &qY2[i]);
    st->update(i);
  }
  st->relax();
  int m;
  scanf("%d", &m);
  const long long mod = 1000000000;
  int past = 0;
  long long ans;
  for (int i = 1; i <= m; i++) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    x = (((long long)past) + ((long long)x)) % mod;
    ans = st->get(l, r, x);
    past = ans % mod;
    printf("%lld\n", ans);
  }
}

```