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;
int a[300003], b[300003], c[300003], f[300003], g[300003], h[300003], i, j,
    l[300003], m, n, o[300003], p[300003], q, r[300003], s[300003], t;
long long d[300003], e[300003], k[300003], z;
int get(int u) { return o[u] ? o[u] = get(o[u]) : u; }
inline bool cmp(int u, int v) { return h[u] < h[v]; }
inline void add(long long* x, int u, int v) {
  while (u <= n) x[u] += v, u += u & -u;
}
inline void del(long long* x, int u, int v) {
  while (u <= n) x[u] -= v, u += u & -u;
}
inline long long sum(long long* x, int u) {
  long long v = 0;
  while (u) v += x[u], u ^= u & -u;
  return v;
}
inline int find(long long v) {
  int u = 0;
  for (j = m; j; j >>= 1)
    if ((u | j) <= n && e[u | j] <= v) v -= e[u |= j];
  return u + 1;
}
inline void modify(int u, int v) {
  while ((u = get(u + 1)) <= v) p[u] = t, o[u] = get(u + 1);
}
int u, v, w, x, y;
int main() {
  for (scanf("%d", &n), memset(d + 1, -1, n - 1 << 3), e[n] = m = 1;
       m << 1 <= n; m <<= 1)
    ;
  for (i = 1; i <= n; i++)
    scanf("%d%d%d", a + i, b + i, c + i),
        h[r[i] = i] = b[i] <= c[i] ? 1
                      : !c[i]      ? 100000000
                                   : (b[i] + c[i] - 1) / c[i];
  for (sort(r + 1, r + n + 1, cmp), scanf("%d", &q), i = 1; i <= q; s[i++] = t)
    for (scanf("%d%d%d", &w, &u, &v),
         x = sum(e, --u), !~d[u] ? d[u] = d[find(x++)], add(e, u, 1), 0 : 0;
         u < v; v == (u = g[t]) ? h[t] = w - d[y], v != y ? add(e, u, 1),
         d[u] = w : d[u] = w : (del(e, u, 1), h[t] = w - d[u], d[u] = -1), t++)
      modify(f[l[t] = t] = u, g[t] = min(v, y = find(x)));
  for (memset(d + 1, 0, n << 3), memset(e + 1, 0, n << 3), i = 1; i <= n; i++)
    if (d[i] += c[i], i + (i & -i) <= n) d[i + (i & -i)] += d[i];
  for (sort(l, l + t, cmp), i = 0, j = 1; i < t;
       k[l[i]] = (sum(d, g[l[i]]) - sum(d, f[l[i]])) * h[l[i]] +
                 sum(e, g[l[i]]) - sum(e, f[l[i]]),
                            i++)
    while (j <= n && b[r[j]] <= (long long)h[l[i]] * c[r[j]])
      del(d, r[j], c[r[j]]), add(e, r[j], b[r[j]]), j++;
  for (i = 1; i <= n; i++)
    if (o[i] && (long long)h[p[i]] * c[i] < b[i])
      k[p[i]] += min(b[i] - c[i] * h[p[i]], a[i]);
  for (i = 1; i <= q; printf("%lld\n", z), i++)
    for (z = 0, j = s[i - 1]; j < s[i]; j++) z += k[j];
  return 0;
}