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;
struct node {
  int now, lim, per, re;
};
int inf = 1000000000;
inline int ceil(int x, int y) {
  if (y == 0) return inf;
  if (x % y == 0) return x / y;
  return x / y + 1;
}
inline node make(int now, int lim, int per, int re) {
  node ans;
  ans.now = now;
  ans.lim = lim;
  ans.per = per;
  ans.re = re;
  return ans;
}
const int MN = 320 + 10;
node tmp[MN];
int n, m, x, y, z, Bl, wh[100010], l, r, Time;
inline bool cmp(int A, int B) { return tmp[A].re < tmp[B].re; }
struct lump {
  node a[MN];
  int n, pretime, st, en, c[MN], s[MN], ss[MN], cc[MN], ps[MN], h1[MN], h2[MN],
      ord[MN], be[MN], C[MN];
  int b[MN];
  long long sum;
  bool clear;
  void push(node x) { a[++n] = x; }
  void first() {
    for (int i = 1; i <= n; i++) {
      tmp[i] = a[i];
      tmp[i].re = ceil(a[i].lim, a[i].per);
      ord[i] = i;
    }
    sort(ord + 1, ord + n + 1, cmp);
    for (int i = 1; i <= n; i++) C[i] = tmp[ord[i]].re;
    for (int i = 1; i <= n; i++) ss[i] = ss[i - 1] + tmp[ord[i]].lim;
    for (int i = 1; i <= n; i++) cc[i] = cc[i - 1] + tmp[ord[i]].per;
  }
  void init() {
    sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += a[i].now;
      a[i].re = ceil(a[i].lim - a[i].now, a[i].per);
      tmp[i] = a[i];
      be[i] = i;
    }
    sort(be + 1, be + n + 1, cmp);
    for (int i = 1; i <= n; i++) b[i] = a[be[i]].re;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[be[i]].lim;
    for (int i = 1; i <= n; i++) c[i] = c[i - 1] + a[be[i]].per;
    for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[be[i]].now;
  }
  void gotime() {
    int undo = Time - pretime;
    if (clear) {
      int p = upper_bound(C + 1, C + n + 1, undo) - C;
      sum = ss[p - 1];
      sum += (long long)undo * (cc[n] - cc[p - 1]);
    } else {
      int p = upper_bound(b + 1, b + n + 1, undo) - b;
      sum = s[p - 1];
      sum += (long long)undo * (c[n] - c[p - 1]) + (ps[n] - ps[p - 1]);
    }
  }
  bool pushdown() {
    bool flag = 0;
    if (clear) {
      for (int i = 1; i <= n; i++) a[i].now = 0;
      clear = 0;
      flag = 1;
    }
    int undo = Time - pretime;
    for (int i = 1; i <= n; i++)
      a[i].now =
          min((long long)undo * a[i].per + a[i].now, (long long)a[i].lim);
    return flag;
  }
  long long puli(int l, int r) {
    bool flag = pushdown();
    long long ans = 0;
    for (int i = l; i <= r; i++) {
      ans += a[i].now;
      a[i].now = 0;
    }
    for (int i = 1; i <= n; i++) a[i].re = ceil(a[i].lim - a[i].now, a[i].per);
    int t1 = 0, t2 = 0;
    sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += a[i].now;
      if (l <= ord[i] && ord[i] <= r) h1[++t1] = ord[i];
      if (flag) {
        if (l > ord[i] || ord[i] > r) h2[++t2] = ord[i];
      } else {
        if (l > be[i] || be[i] > r) h2[++t2] = be[i];
      }
    }
    int i = 1, j = 1, t = 0;
    while (i <= t1 || j <= t2) {
      if (j > t2 || (i <= t1 && a[h1[i]].re <= a[h2[j]].re))
        be[++t] = h1[i++];
      else
        be[++t] = h2[j++];
    }
    for (int i = 1; i <= n; i++) b[i] = a[be[i]].re;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[be[i]].lim;
    for (int i = 1; i <= n; i++) c[i] = c[i - 1] + a[be[i]].per;
    for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[be[i]].now;
    pretime = Time;
    return ans;
  }
} B[350];
void read(int &x) {
  char ch = getchar();
  int mark = 1;
  for (; ch != '-' && (ch < '0' || ch > '9'); ch = getchar())
    ;
  if (ch == '-') mark = -1, ch = getchar();
  for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  x *= mark;
}
int main() {
  read(n);
  int cnt = 320, c = 0;
  Bl = 1;
  for (int i = 1; i <= n; i++) {
    read(x);
    read(y);
    read(z);
    c++;
    B[Bl].push(make(x, y, z, ceil(y - x, z)));
    wh[i] = Bl;
    if (c == cnt) {
      c = 0;
      Bl++;
    }
  }
  for (int i = 1; i <= Bl; i++) B[i].first(), B[i].init();
  c = 1;
  for (int i = 1; i <= Bl; i++) {
    B[i].st = c;
    B[i].en = min(n, c + cnt - 1);
    c += cnt;
  }
  read(m);
  for (; m--;) {
    read(x);
    read(l);
    read(r);
    Time = x;
    int L = wh[l], R = wh[r];
    long long ans = 0;
    if (L == R)
      ans = B[L].puli(l - B[L].st + 1, r - B[L].st + 1);
    else {
      if (l - B[L].st + 1 != 1)
        ans += B[L].puli(l - B[L].st + 1, B[L].n);
      else
        L--;
      if (r - B[R].st + 1 != B[R].n)
        ans += B[R].puli(1, r - B[R].st + 1);
      else
        R++;
      for (int i = L + 1; i < R; i++) {
        B[i].gotime();
        ans += B[i].sum;
        B[i].sum = 0;
        B[i].clear = 1;
        B[i].pretime = Time;
      }
    }
    printf("%I64d\n", ans);
  }
}