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;
const int maxn = 2e6 + 10;
inline int read() {
  int data = 0, f = 1;
  char c = getchar();
  while ('0' > c || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    data = data * 10 + c - '0';
    c = getchar();
  }
  return data * f;
}
int n, M, rt[maxn], shu;
long long ti[maxn];
long long q[maxn], m[maxn], h[maxn];
struct node {
  int l, r;
  long long t;
} a[maxn];
struct node2 {
  int ls, rs;
  long long s, s1;
} t[maxn << 1];
int cnt, num;
set<node> s;
void mo(int &rt, int o, int l, int r, int p, int i) {
  rt = ++cnt;
  t[rt] = t[o];
  t[rt].s += m[i];
  t[rt].s1 += h[i];
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    mo(t[rt].ls, t[o].ls, l, mid, p, i);
  else
    mo(t[rt].rs, t[o].rs, mid + 1, r, p, i);
}
bool operator<(node a, node b) { return a.l < b.l; }
long long qu1(int rt, int o, int l, int r, int nl, int nr) {
  if (nl <= l && r <= nr) {
    return t[rt].s - t[o].s;
  }
  int mid = (l + r) >> 1;
  long long SUM = 0;
  if (nl <= mid) SUM += qu1(t[rt].ls, t[o].ls, l, mid, nl, nr);
  if (nr > mid) SUM += qu1(t[rt].rs, t[o].rs, mid + 1, r, nl, nr);
  return SUM;
}
long long qu2(int rt, int o, int l, int r, int nl, int nr) {
  if (nl <= l && r <= nr) {
    return t[rt].s1 - t[o].s1;
  }
  int mid = (l + r) >> 1;
  long long SUM = 0;
  if (nl <= mid) SUM += qu2(t[rt].ls, t[o].ls, l, mid, nl, nr);
  if (nr > mid) SUM += qu2(t[rt].rs, t[o].rs, mid + 1, r, nl, nr);
  return SUM;
}
vector<node> v;
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    q[i] = read(), m[i] = read(), h[i] = read();
    if (h[i])
      ti[i] = (m[i] - 1) / h[i] + 1;
    else {
      ti[i] = 1e10;
    }
  }
  sort(ti + 1, ti + n + 1);
  shu = unique(ti + 1, ti + n + 1) - ti - 1;
  for (int i = 1; i <= n; ++i) {
    int ji;
    if (h[i]) {
      ji = lower_bound(ti + 1, ti + shu + 1, (m[i] - 1) / h[i] + 1) - ti;
    } else {
      ji = shu;
    }
    mo(rt[i], rt[i - 1], 1, shu, ji, i);
  }
  for (int i = 1; i <= n; ++i) {
    node x;
    x.l = x.r = i;
    x.t = 0;
    s.insert(x);
  }
  M = read();
  while (M--) {
    int t, l, r;
    t = read(), l = read(), r = read();
    set<node>::iterator it;
    node x;
    x.l = l, x.r = r, x.t = t;
    it = s.upper_bound(x);
    --it;
    num = 0;
    while (1) {
      if (it == s.end() || (*it).l > r) break;
      v.push_back((*it));
      ++num;
      ++it;
    }
    for (int i = 0; i < num; ++i) s.erase(s.find(v[i]));
    if (v[0].l < l) {
      node y;
      y.l = v[0].l;
      y.r = l - 1;
      y.t = v[0].t;
      v[0].l = l;
      s.insert(y);
    }
    if (v[num - 1].r > r) {
      node y;
      y.l = r + 1, y.r = v[num - 1].r, y.t = v[num - 1].t;
      v[num - 1].r = r;
      s.insert(y);
    }
    x.l = l, x.r = r, x.t = t;
    s.insert(x);
    long long ans = 0;
    for (int i = 0; i < num; ++i) {
      x = v[i];
      if (x.t) {
        int ji = upper_bound(ti + 1, ti + shu + 1, t - x.t) - ti - 1;
        if (ji != 0) {
          ans += qu1(rt[x.r], rt[x.l - 1], 1, shu, 1, ji);
        }
        ans += qu2(rt[x.r], rt[x.l - 1], 1, shu, ji + 1, shu) * (t - x.t);
      } else {
        ans += min(q[x.l] + t * h[x.l], m[x.l]);
      }
    }
    v.clear();
    cout << ans << "\n";
  }
  return 0;
}