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 int read() {
  int x = 0, 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();
  }
  return x * f;
}
struct data {
  int l, r, t, x;
  data(int _l, int _r, int _t, int _x) {
    l = _l;
    r = _r;
    t = _t;
    x = _x;
  }
  data(int k) {
    l = k;
    r = 0;
  }
  bool operator<(const data& b) const { return l == b.l ? r < b.r : l < b.l; }
};
set<data> s;
long long Ans[100000 + 5], T1[131072 * 2 + 5], T2[131072 * 2 + 5];
int n, m, top, a[100000 + 5], mx[100000 + 5], R[100000 + 5], rk[100000 + 5],
    tms[100000 + 5];
struct ques {
  int l, r, t, id;
} q[100000 * 10 + 5];
int Calc(int t, int x, int r, int m) {
  return (int)min((long long)m, x + 1LL * r * t);
}
bool cmp(const ques& a, const ques& b) { return a.t < b.t; }
bool cmp2(int x, int y) { return tms[x] < tms[y]; }
void Renew(long long* T, int x, int v) {
  for (T[x += 131072] += v; x >>= 1;) T[x] = T[x << 1] + T[x << 1 | 1];
}
long long Query(long long* T, int l, int r) {
  long long sum = 0;
  for (l += 131072 - 1, r += 131072 + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
    if (~l & 1) sum += T[l + 1];
    if (r & 1) sum += T[r - 1];
  }
  return sum;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    mx[i] = read();
    R[i] = read();
    tms[i] = R[i] ? (int)ceil((double)mx[i] / R[i]) : 2e9;
    s.insert(data(i, i, 0, a[i]));
    rk[i] = i;
  }
  m = read();
  for (int i = 1; i <= m; ++i) {
    int t = read(), l = read(), r = read();
    set<data>::iterator it = s.lower_bound(data(l));
    for (; it != s.end() && it->l <= r; it = s.lower_bound(data(l))) {
      if (it->r > r) s.insert(data(r + 1, it->r, it->t, it->x));
      if (it->r == it->l)
        Ans[i] += Calc(t - it->t, it->x, R[it->r], mx[it->r]);
      else
        q[++top] = (ques){it->l, min(it->r, r), t - it->t, i};
      s.erase(it);
    }
    for (; it != s.begin() && (--it)->r >= l; it = s.lower_bound(data(l))) {
      if (it->r > r) s.insert(data(r + 1, it->r, it->t, it->x));
      if (it->l < l) s.insert(data(it->l, l - 1, it->t, it->x));
      q[++top] = (ques){max(it->l, l), min(r, it->r), t - it->t, i};
      s.erase(it);
    }
    s.insert(data(l, r, t, 0));
  }
  sort(rk + 1, rk + n + 1, cmp2);
  sort(q + 1, q + top + 1, cmp);
  for (int i = 1; i <= n; ++i) Renew(T1, i, R[i]);
  for (int i = 1, j = 1; i <= top;)
    if (j <= n && tms[rk[j]] <= q[i].t) {
      Renew(T1, rk[j], -R[rk[j]]);
      Renew(T2, rk[j], mx[rk[j]]);
      ++j;
    } else {
      Ans[q[i].id] +=
          1LL * q[i].t * Query(T1, q[i].l, q[i].r) + Query(T2, q[i].l, q[i].r);
      ++i;
    }
  for (int i = 1; i <= m; ++i) printf("%lld\n", Ans[i]);
  return 0;
}