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 N = 1e5 + 5, M = 1800005, INF = 1e9;
int s[N], h[N], m[N], c, d, g[N], l[N], n, r[N];
long long p[N];
struct note {
  int l, r;
  long long s, z;
} e[M];
struct qj {
  int l, t;
  bool operator<(const qj &a) const { return l == a.l ? t < a.t : l < a.l; }
};
set<qj> t;
bool cmp(int x, int y) {
  return 1ll * (m[x] - 1) * h[y] < 1ll * (m[y] - 1) * h[x];
}
int lsh(int x) { return lower_bound(r + 1, r + c + 1, x) - r; }
void add(int p, int &k, int l, int r, int x) {
  if (x < l || r < x) return;
  e[k = ++d] = e[p];
  if (l == r) {
    e[k].s = h[l], e[k].z = m[l];
    return;
  }
  int m = (l + r) >> 1;
  add(e[p].l, e[k].l, l, m, x);
  add(e[p].r, e[k].r, m + 1, r, x);
  e[k].s = e[e[k].l].s + e[e[k].r].s;
  e[k].z = e[e[k].l].z + e[e[k].r].z;
}
long long ask(int k, int l, int r, int x, int y, int v) {
  if (!k) return 0;
  if (y < l || r < x) return 0;
  if (x <= l && r <= y) return e[k].s * v - e[k].z;
  int m = (l + r) >> 1;
  return ask(e[k].l, l, m, x, y, v) + ask(e[k].r, m + 1, r, x, y, v);
}
long long query(int x, int y, int p, int t) {
  if (p) return ask(g[c - lsh(t - p) + 1], 1, n, x, y - 1, t - p);
  long long a = 0;
  for (int i = x; i < y; i++) {
    if (m[i] > 1ll * h[i] * t + s[i]) a += h[i] * t + s[i] - m[i];
    if (!h[i]) a += s[i];
  }
  return a;
}
int main() {
  qj u;
  int o, x, y, q;
  long long a;
  set<qj>::iterator it1, it2, it, nx;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &s[i], &m[i], &h[i]);
    if (!h[i]) m[i] = 0;
    p[i] = p[i - 1] + m[i];
    if (h[i] && (m[i] - 1) / h[i] > 0) l[++c] = i;
  }
  sort(l + 1, l + c + 1, cmp);
  for (int i = c; i; i--) {
    r[i] = (m[l[i]] - 1) / h[l[i]];
    add(g[c - i], g[c - i + 1], 1, n, l[i]);
  }
  u.l = 1, u.t = 0;
  t.insert(u);
  u.l = n + 1, u.t = 0;
  t.insert(u);
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d", &o, &x, &y);
    a = 0;
    u.l = x, u.t = INF;
    it1 = --t.upper_bound(u);
    u.l = y, u.t = INF;
    it2 = --t.upper_bound(u);
    nx = it = it1, nx++;
    for (; it != it2; it = nx, nx++) {
      if (it == it1)
        a = query(x, nx->l, it->t, o);
      else
        a += query(it->l, nx->l, it->t, o);
      if (it != it1 || it->l == x) t.erase(it);
    }
    if (y + 1 < (nx->l)) u.l = y + 1, u.t = it->t, t.insert(u);
    u.l = x, u.t = o;
    t.insert(u);
    if (it1 == it2) {
      a = query(x, y + 1, it->t, o);
      if (it->l == x) t.erase(it);
    } else {
      a += query(it->l, y + 1, it->t, o);
      t.erase(it);
    }
    printf("%lld\n", a + p[y] - p[x - 1]);
  }
}