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;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void judge() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
const int maxn = 200005;
int n, Q, s[maxn], m[maxn], t[maxn], l[maxn], r[maxn], R[maxn];
set<pair<pair<int, int>, int> > res;
namespace seg {
long long suma[maxn << 5], sumb[maxn << 5];
int ls[maxn << 5], rs[maxn << 5], tot;
inline void update(int x) {
  suma[x] = suma[ls[x]] + suma[rs[x]];
  sumb[x] = sumb[ls[x]] + sumb[rs[x]];
}
inline void add(int x, int &y, int place, int va, int vb, int l, int r) {
  y = ++tot;
  suma[y] = suma[x];
  sumb[y] = sumb[x];
  ls[y] = ls[x];
  rs[y] = rs[x];
  suma[y] += va;
  sumb[y] += vb;
  if (l == r) {
    return;
  }
  int md = (l + r) >> 1;
  if (place <= md)
    add(ls[x], ls[y], place, va, vb, l, md);
  else
    add(rs[x], rs[y], place, va, vb, md + 1, r);
}
inline long long queryA(int x, int l, int r, int lq, int rq) {
  if (!x) return 0;
  if (lq <= l && r <= rq) return suma[x];
  long long res = 0;
  int md = (l + r) >> 1;
  if (lq <= md) res += queryA(ls[x], l, md, lq, rq);
  if (rq > md) res += queryA(rs[x], md + 1, r, lq, rq);
  return res;
}
inline long long queryB(int x, int l, int r, int lq, int rq) {
  if (!x) return 0;
  if (lq <= l && r <= rq) return sumb[x];
  long long res = 0;
  int md = (l + r) >> 1;
  if (lq <= md) res += queryB(ls[x], l, md, lq, rq);
  if (rq > md) res += queryB(rs[x], md + 1, r, lq, rq);
  return res;
}
}  // namespace seg
int qtot = 0;
int root[maxn];
inline long long query(int l, int r, int tme) {
  tme = min(tme, 99999);
  return seg::queryA(root[r], 0, 100001, 0, tme) -
         seg::queryA(root[l - 1], 0, 100001, 0, tme) +
         1ll *
             (seg::queryB(root[r], 0, 100001, tme + 1, 100001) -
              seg::queryB(root[l - 1], 0, 100001, tme + 1, 100001)) *
             tme;
}
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(s[i]), read(m[i]), read(R[i]);
  for (int i = (1); i <= (n); i++) res.insert(make_pair(make_pair(i, i), -1));
  fprintf(stderr, "%d %d %d\n", s[39], m[39], R[39]);
  read(Q);
  for (int i = (1); i <= (Q); i++) read(t[i]), read(l[i]), read(r[i]);
  for (int i = (1); i <= (n); i++) {
    if (R[i] == 0) {
      seg::add(root[i - 1], root[i], 100001, 0, R[i], 0, 100001);
      continue;
    }
    int t = floor((long double)m[i] / R[i] + 0.99999999);
    if (i == 39) fprintf(stderr, "%d\n", t);
    assert(1ll * t * R[i] >= m[i]);
    assert(1ll * (t - 1) * R[i] < m[i]);
    seg::add(root[i - 1], root[i], t, m[i], R[i], 0, 100001);
  }
  for (int i = (1); i <= (Q); i++) {
    long long ans = 0;
    if (i == 82259) fprintf(stderr, "%d %d %d\n", l[i], r[i], t[i]);
    set<pair<pair<int, int>, int> >::iterator it =
        res.upper_bound(make_pair(make_pair(l[i], n + 1), 1));
    vector<set<pair<pair<int, int>, int> >::iterator> rubi;
    rubi.clear();
    it--;
    if (it->first.first < l[i]) {
      res.insert(make_pair(make_pair(it->first.first, l[i] - 1), it->second));
    }
    int tmp1 = it->first.second, tmp2 = it->second;
    res.erase(it);
    res.insert(make_pair(make_pair(l[i], tmp1), tmp2));
    it = res.upper_bound(make_pair(make_pair(l[i], n + 1), 1));
    it--;
    for (;;) {
      if (i == 82259)
        fprintf(stderr, "%d %d %d\n", it->first.first, it->first.second,
                it->second);
      if (it->second == -1) {
        assert(it->first.first == it->first.second);
        ans += min(
            (long long)m[it->first.first],
            (long long)s[it->first.first] + 1ll * R[it->first.first] * t[i]);
      } else {
        ans += query(it->first.first, min(it->first.second, r[i]),
                     t[i] - it->second);
        if (i == 82259)
          fprintf(stderr, "* %lld\n",
                  query(it->first.first, min(it->first.second, r[i]),
                        t[i] - it->second));
        long long res = 0;
      }
      rubi.push_back(it);
      if (it->first.second > r[i]) {
        res.insert(
            make_pair(make_pair(r[i] + 1, it->first.second), it->second));
        break;
      }
      if (it->first.second == r[i]) break;
      it++;
    }
    for (set<pair<pair<int, int>, int> >::iterator x : rubi) res.erase(x);
    res.insert(make_pair(make_pair(l[i], r[i]), t[i]));
    cout << ans << endl;
  }
  return 0;
}