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;
void getint(int &v) {
  char ch, fu = 0;
  for (ch = '*'; (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  if (ch == '-') fu = 1, ch = getchar();
  for (v = 0; ch >= '0' && ch <= '9'; ch = getchar()) v = v * 10 + ch - '0';
  if (fu) v = -v;
}
struct node {
  int l, r, t;
  node() {}
  node(int L, int R, int T) { l = L, r = R, t = T; }
  bool operator<(const node &A) const {
    return (l < A.l || l == A.l && r < A.r || l == A.l && r == A.r && t < A.t);
  }
};
set<node> S;
pair<long long, long long> T[5000010];
node tmp[500010];
long long ans;
int n, ts, q, s[500010], m[500010], ls[5000010], tot, rs[5000010], a[500010],
    rot[500010], r[500010];
void ins(int rt1, int &rt2, int l, int r, int x, pair<long long, long long> t) {
  if (!rt2) rt2 = ++tot;
  T[rt2] = T[rt1];
  T[rt2].first += t.first;
  T[rt2].second += t.second;
  ls[rt2] = ls[rt1];
  rs[rt2] = rs[rt1];
  if (l == r) return;
  int m = l + r >> 1;
  if (x <= m)
    ins(ls[rt1], ls[rt2] = ++tot, l, m, x, t);
  else
    ins(rs[rt1], rs[rt2] = ++tot, m + 1, r, x, t);
}
pair<long long, long long> que(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) return T[rt];
  int m = l + r >> 1;
  pair<long long, long long> t = make_pair(0ll, 0ll);
  if (L <= m) {
    pair<long long, long long> tmp = que(ls[rt], l, m, L, R);
    t.first += tmp.first;
    t.second += tmp.second;
  }
  if (R > m) {
    pair<long long, long long> tmp = que(rs[rt], m + 1, r, L, R);
    t.first += tmp.first;
    t.second += tmp.second;
  }
  return t;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    getint(s[i]), getint(m[i]), getint(r[i]);
    if (m[i] == 0)
      a[i] = 0;
    else if (r[i] == 0)
      a[i] = 100001;
    else if (m[i] % r[i] == 0)
      a[i] = m[i] / r[i];
    else
      a[i] = m[i] / r[i] + 1;
  }
  rot[0] = 0;
  for (int i = 1; i <= n; ++i)
    ins(rot[i - 1], rot[i], 0, 100001, a[i], make_pair(r[i], m[i]));
  for (int i = 1; i <= n; ++i) S.insert(node(i, i, -1));
  cin >> q;
  while (q--) {
    int ti, le, ri;
    getint(ti), getint(le), getint(ri);
    set<node>::iterator it = S.lower_bound(node(le + 1, 0, 0));
    --it;
    if ((it->l) != le) {
      node t = *it;
      S.erase(it);
      S.insert(node(t.l, le - 1, t.t));
      S.insert(node(le, t.r, t.t));
    }
    it = S.lower_bound(node(ri + 1, 0, 0));
    --it;
    if ((it->r) != ri) {
      node t = *it;
      S.erase(it);
      S.insert(node(t.l, ri, t.t));
      S.insert(node(ri + 1, t.r, t.t));
    }
    it = S.lower_bound(node(le + 1, 0, 0));
    --it;
    ans = 0;
    ts = 0;
    while (1) {
      node t = *it;
      tmp[++ts] = t;
      if (t.t == -1) {
        int now = (int)min(1ll * ti * r[t.l] + s[t.l], 1ll * m[t.l]);
        ans += now;
      } else {
        int re = ti - t.t;
        re = min(re, 100000);
        long long t1 = que(rot[t.r], 0, 100001, 0, re).second -
                       que(rot[t.l - 1], 0, 100001, 0, re).second;
        ans += t1;
        long long t2 = que(rot[t.r], 0, 100001, re + 1, 100001).first -
                       que(rot[t.l - 1], 0, 100001, re + 1, 100001).first;
        ans += t2 * re;
      }
      if ((it->r) == ri) break;
      ++it;
    }
    printf("%lld\n", ans);
    while (ts) {
      S.erase(S.find(node(tmp[ts].l, tmp[ts].r, tmp[ts].t)));
      --ts;
    }
    S.insert(node(le, ri, ti));
  }
  return 0;
}