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 RI() {}
template <typename... T>
void RI(int &head, T &...tail) {
  scanf("%d", &head);
  RI(tail...);
}
const int BN = 100010 / 120 + 514;
int n, st[100010], mx[100010], re[100010];
struct P {
  int t;
  long long v, d;
};
struct Block {
  int l, r, last, sre;
  bool zero;
  vector<P> vp, vpz;
  void build() {
    if (zero && !vpz.empty()) return;
    auto &vv = zero ? vpz : vp;
    vector<pair<int, int> > evt;
    for (int i = (l); i <= int(r); i++)
      if (re[i] > 0) {
        evt.push_back(make_pair((mx[i] - st[i] + re[i] - 1) / re[i], i));
      }
    sort(begin(evt), end(evt));
    vv.clear();
    int ne = ((int)(evt).size());
    long long v = 0, d = sre;
    for (int i = (l); i <= int(r); i++) v += st[i];
    vv.push_back(P{0, v, d});
    for (int i = 0, j; i < ne; i = j) {
      int t = evt[i].first;
      v += (t - (i > 0 ? evt[i - 1].first : 0)) * d;
      for (j = i; j < ne && evt[j].first == t; j++) {
        int w = evt[j].second;
        d -= re[w];
        v -= re[w] - (mx[w] - (st[w] + (t - 1) * re[w]));
      }
      vv.push_back(P{t, v, d});
    }
  }
  long long get(int t) {
    auto &v = zero ? vpz : vp;
    t -= last;
    last += t;
    int ll = 0, rr = ((int)(v).size()) - 1;
    while (ll != rr) {
      int mm = (ll + rr + 1) / 2;
      if (v[mm].t > t)
        rr = mm - 1;
      else
        ll = mm;
    }
    long long ret = v[ll].v + (t - v[ll].t) * v[ll].d;
    if (!zero) {
      zero = 1;
      for (int i = (l); i <= int(r); i++) st[i] = 0;
    }
    build();
    return ret;
  }
  void flat(int t) {
    zero = 0;
    t -= last;
    last += t;
    for (int i = (l); i <= int(r); i++)
      st[i] = min((long long)mx[i], st[i] + (long long)t * re[i]);
  }
} blk[BN];
int main() {
  RI(n);
  for (int i = (1); i <= int(n); i++) RI(st[i], mx[i], re[i]);
  int bn = 0;
  for (int i = 1; i <= n; i += 120) {
    auto &b = blk[bn];
    b.l = i;
    b.r = min(n, i + 120 - 1);
    b.sre = b.last = b.zero = 0;
    for (int j = (b.l); j <= int(b.r); j++) b.sre += re[j];
    bn++;
  }
  for (int i = 0; i < int(bn); i++) blk[i].build();
  int m;
  RI(m);
  while (m--) {
    int t, l, r;
    RI(t, l, r);
    long long ans = 0;
    for (int i = 0; i < int(bn); i++) {
      auto &b = blk[i];
      if (r < b.l || b.r < l) continue;
      if (l <= b.l && b.r <= r) {
        ans += b.get(t);
      } else {
        b.flat(t);
        int lb = max(l, b.l);
        int rb = min(r, b.r);
        for (int j = (lb); j <= int(rb); j++) {
          ans += st[j];
          st[j] = 0;
        }
        b.build();
      }
    }
    cout << ans << "\n";
  }
  return 0;
}