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 gi() {
  char c;
  int num = 0, flg = 1;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flg = -1;
  while (c >= '0' && c <= '9') {
    num = num * 10 + c - 48;
    c = getchar();
  }
  return num * flg;
}
struct anode {
  int s, m, r;
} val[100005];
long long sumr[100005];
struct qnode {
  int l, r, t;
  qnode() {}
  qnode(int a, int b, int c) {
    l = a;
    r = b;
    t = c;
  }
  bool operator<(const qnode &T) const { return l < T.l; }
};
set<qnode> S;
set<qnode>::iterator split(int x) {
  set<qnode>::iterator it = S.lower_bound(qnode(x, x, 0));
  if (it != S.end() && (*it).l == x) return it;
  qnode tmp = *--it;
  S.erase(it);
  S.insert(qnode(tmp.l, x - 1, tmp.t));
  it = S.insert(qnode(x, tmp.r, tmp.t)).first;
  return it;
}
struct node {
  int l, r;
  long long sm, sr;
} a[100005 * 19];
int T[100005], tot;
void insert(int &i, int pre, int l, int r, int x, int km, int kr) {
  if (i == pre) i = ++tot, a[i] = a[pre];
  a[i].sm += km;
  a[i].sr += kr;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    insert(a[i].l, a[pre].l, l, mid, x, km, kr);
  else
    insert(a[i].r, a[pre].r, mid + 1, r, x, km, kr);
}
pair<long long, long long> query(int i, int l, int r, int ql, int qr) {
  if (!i || l > qr || r < ql) return make_pair(0ll, 0ll);
  if (ql <= l && r <= qr) return make_pair(a[i].sm, a[i].sr);
  int mid = (l + r) >> 1;
  pair<long long, long long> lans = query(a[i].l, l, mid, ql, qr);
  pair<long long, long long> rans = query(a[i].r, mid + 1, r, ql, qr);
  return make_pair(lans.first + rans.first, lans.second + rans.second);
}
const int lim = 100000;
int main() {
  int n, i, m, x, y, t;
  n = gi();
  S.insert(qnode(n + 1, 2 * lim, 0));
  S.insert(qnode(0, 0, 0));
  for (i = 1; i <= n; i++) {
    val[i].s = gi();
    val[i].m = gi();
    val[i].r = gi();
    sumr[i] = sumr[i - 1] + 1ll * val[i].r;
    S.insert(qnode(i, i, 0));
    T[i] = T[i - 1];
    if (val[i].r)
      insert(T[i], T[i - 1], 0, lim,
             (val[i].m / val[i].r + (val[i].m % val[i].r != 0)), val[i].m,
             val[i].r);
  }
  m = gi();
  for (i = 1; i <= m; i++) {
    t = gi();
    x = gi();
    y = gi();
    set<qnode>::iterator r = split(y + 1), l = split(x);
    long long ans = 0;
    for (set<qnode>::iterator it = l; it != r; it++) {
      qnode tmp = *it;
      if (tmp.t == 0)
        ans += min(1ll * val[tmp.l].m, val[tmp.l].s + 1ll * t * val[tmp.l].r);
      else {
        tmp.l--;
        pair<long long, long long> retl = query(T[tmp.l], 0, lim, 0, t - tmp.t);
        pair<long long, long long> ret = query(T[tmp.r], 0, lim, 0, t - tmp.t);
        ret.first -= retl.first;
        ret.second -= retl.second;
        ans += 1ll * (t - tmp.t) * ((sumr[tmp.r] - sumr[tmp.l]) - ret.second) +
               ret.first;
      }
    }
    S.erase(l, r);
    S.insert(qnode(x, y, t));
    printf("%lld\n", ans);
  }
}