Problem: Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series "My Little Pony: Friendship Is Magic". In "Twilight's Kingdom" (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.

<image>

The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.

Now to simplify the problem, assume you have n ponies (numbered from 1 to n). Each pony has three attributes:

  * si : amount of mana that the pony has at time 0; 
  * mi : maximum mana that the pony can have; 
  * ri : mana regeneration per unit time. 



Lord Tirek will do m instructions, each of them can be described with three integers: ti, li, ri. The instruction means that at time ti, Tirek will use Absorb Mana on ponies with numbers from li to ri (both borders inclusive). We'll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of ponies. Each of the next n lines contains three integers si, mi, ri (0 ≤ si ≤ mi ≤ 105; 0 ≤ ri ≤ 105), describing a pony. 

The next line contains an integer m (1 ≤ m ≤ 105) — the number of instructions. Each of the next m lines contains three integers ti, li, ri (0 ≤ ti ≤ 109; 1 ≤ li ≤ ri ≤ n), describing an instruction of Lord Tirek. The instructions are given in strictly increasing order of ti (all ti are distinct).

Output

For each instruction, output a single line which contains a single integer, the total mana absorbed in this instruction.

Examples

Input

5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5


Output

25
58

Note

Every pony starts with zero mana. For the first instruction, each pony has 5 mana, so you get 25 mana in total and each pony has 0 mana after the first instruction.

For the second instruction, pony 3 has 14 mana and other ponies have mana equal to their mi.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
struct Pony {
  int lim, rate;
  int untilFull(int cur) const {
    if (rate == 0) {
      return INT_MAX;
    } else {
      return (lim - cur + rate - 1) / rate;
    }
  }
  int untilFull() const {
    if (rate == 0) {
      return INT_MAX;
    } else {
      return (lim + rate - 1) / rate;
    }
  }
  bool operator<(const Pony& o) const { return untilFull() < o.untilFull(); }
};
template <class F>
int search(int l, int r, F test) {
  r++;
  while (r - l > 1) {
    int m = l + r >> 1;
    if (test(m))
      l = m;
    else
      r = m;
  }
  return test(l) ? l : l - 1;
}
struct Node {
  vector<Pony> v;
  vector<long long> sumRate, sumCapacity;
  void reset(int n) {
    v.resize(n);
    sumRate.resize(n);
    sumCapacity.resize(n);
  }
  long long query(int time) {
    int i = search(0, v.size() - 1,
                   [&](int i) { return v[i].untilFull() <= time; });
    long long ans;
    if (i == -1) {
      ans = sumRate.front() * time;
    } else if (i == v.size() - 1) {
      ans = sumCapacity.back();
    } else {
      ans = sumCapacity[i] + sumRate[i + 1] * time;
    }
    return ans;
  }
  void leaf(const Pony& p) {
    v.resize(1, p);
    sumRate.resize(1, p.rate);
    sumCapacity.resize(1, p.lim);
  }
  void build(const Node& l, const Node& r) {
    reset(l.v.size() + r.v.size());
    merge(l.v.begin(), l.v.end(), r.v.begin(), r.v.end(), v.begin());
    sumCapacity.front() = v.front().lim;
    for (int i = 1; i < v.size(); i++) {
      sumCapacity[i] = sumCapacity[i - 1] + v[i].lim;
    }
    sumRate.back() = v.back().rate;
    for (int i = v.size() - 2; i >= 0; i--) {
      sumRate[i] = sumRate[i + 1] + v[i].rate;
    }
  }
};
struct SegmentTree {
  int first, last;
  vector<Node> tree;
  SegmentTree(int n, bool base, const vector<Pony>& v)
      : tree(n << 2), first(base), last(n - 1 + base) {
    build(1, first, last, v);
  }
  void build(int i, int l, int r, const vector<Pony>& v) {
    if (l == r) {
      tree[i].leaf(v[l]);
    } else {
      int m = l + r >> 1;
      int lc = i << 1, rc = (i << 1) + 1;
      build(lc, l, m, v);
      build(rc, m + 1, r, v);
      tree[i].build(tree[lc], tree[rc]);
    }
  }
  long long query(int i, int l, int r, int ql, int qr, int delta) {
    if (r < ql || l > qr) {
      return 0;
    } else if (ql <= l && r <= qr) {
      return tree[i].query(delta);
    } else {
      int m = l + r >> 1;
      int lc = i << 1, rc = (i << 1) + 1;
      return query(lc, l, m, ql, qr, delta) +
             query(rc, m + 1, r, ql, qr, delta);
    }
  }
  long long query(int l, int r, int delta) {
    return query(1, first, last, l, r, delta);
  }
};
template <class T>
struct DisjointRanges {
  map<int, pair<int, T>> s;
  vector<pair<int, pair<int, T>>> update(int l, int r, T x) {
    vector<pair<int, pair<int, T>>> bye;
    auto last = s.upper_bound(r);
    if (last != s.begin()) {
      auto it = prev(last);
      if (it->second.first > r) {
        last = s.emplace_hint(last, r + 1, it->second);
        it->second.first = r;
      }
    }
    auto first = s.lower_bound(l);
    if (first != s.begin()) {
      auto it = prev(first);
      if (it->second.first >= l) {
        bye.emplace_back(l, it->second);
        it->second.first = l - 1;
      }
    }
    while (first != last) {
      bye.push_back(*first);
      first = s.erase(first);
    }
    s.emplace_hint(last, l, make_pair(r, x));
    return bye;
  }
};
int main() {
  int n, m;
  scanf("%d", &n);
  vector<Pony> v(n + 1);
  vector<int> init(n + 1);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d %d", &init[i], &v[i].lim, &v[i].rate);
  }
  SegmentTree st(n, 1, v);
  DisjointRanges<int> dr;
  scanf("%d", &m);
  while (m--) {
    int now, ul, ur;
    scanf("%d %d %d", &now, &ul, &ur);
    vector<pair<int, pair<int, int>>> bye = dr.update(ul, ur, now);
    int prev = ul;
    long long ans = 0;
    for (auto& it : bye) {
      int ql = it.first;
      auto [qr, last] = it.second;
      if (ql > prev) {
        for (int i = prev; i < ql; i++) {
          ans += v[i].untilFull(init[i]) <= now
                     ? v[i].lim
                     : init[i] + (long long)v[i].rate * now;
        }
      }
      ans += st.query(ql, qr, now - last);
      prev = qr + 1;
    }
    for (int i = prev; i <= ur; i++) {
      ans += v[i].untilFull(init[i]) <= now
                 ? v[i].lim
                 : init[i] + (long long)v[i].rate * now;
    }
    printf("%lld\n", ans);
  }
}