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 p[18][131072 + 1], P[18][131072 + 1];
long long q[18][131072 + 1], Q[18][131072 + 1], w[18][131072 + 1],
    W[18][131072 + 1], e[18][131072 + 1];
int a[131072 * 2], L[131072 * 2], R[131072 * 2], h[131072 * 2], s[131072],
    t[131072], g[131072], n, m, x, l, r;
inline bool cmp1(const int &x, const int &y) {
  if (!g[x]) return 0;
  if (!g[y]) return 1;
  return t[x] / g[x] < t[y] / g[y];
}
inline bool cmp2(const int &x, const int &y) {
  if (!g[x]) return 0;
  if (!g[y]) return 1;
  return (t[x] - s[x]) / g[x] < (t[y] - s[y]) / g[y];
}
inline void dw(int x) {
  if (a[x] >= -1) a[x * 2] = a[x * 2 + 1] = a[x];
}
inline void up(int x) {
  if (a[x * 2] == a[x * 2 + 1])
    a[x] = a[x * 2];
  else
    a[x] = -2;
}
long long f(int x, int y, int l, int r) {
  if (l == L[x] && r == R[x] && a[x] >= -1) {
    int ls = y - a[x], T = x, M;
    if (a[x] == -1) {
      ls = a[x] = y;
      while (L[T] != R[T]) {
        T *= 2;
        M = P[h[x]][R[T]];
        if (g[M] && (t[M] - s[M]) / g[M] < ls) T++;
      }
      M = P[h[x]][R[T]];
      if (g[M] && (t[M] - s[M]) / g[M] < ls) return Q[h[x]][R[x]];
      if (L[T] == L[x]) return W[h[x]][L[x]] * ls + e[h[x]][L[x]];
      return Q[h[x]][R[T] - 1] + W[h[x]][R[T]] * ls + e[h[x]][R[T]];
    }
    a[x] = y;
    while (L[T] != R[T]) {
      T *= 2;
      M = p[h[x]][R[T]];
      if (g[M] && t[M] / g[M] < ls) T++;
    }
    M = p[h[x]][R[T]];
    if (g[M] && t[M] / g[M] < ls) return q[h[x]][R[x]];
    if (L[T] == L[x]) return w[h[x]][L[x]] * ls;
    return q[h[x]][R[T] - 1] + w[h[x]][R[T]] * ls;
  }
  dw(x);
  long long X;
  if (r <= R[x * 2])
    X = f(x * 2, y, l, r);
  else if (l >= L[x * 2 + 1])
    X = f(x * 2 + 1, y, l, r);
  else
    X = f(x * 2, y, l, R[x * 2]) + f(x * 2 + 1, y, L[x * 2 + 1], r);
  up(x);
  return (X);
}
int main() {
  scanf("%d", &n);
  for (int i = (1); i <= (n); i++) scanf("%d%d%d", &s[i], &t[i], &g[i]);
  L[1] = 1;
  R[1] = 131072;
  h[1] = 0;
  for (int i = (1); i <= (131072 - 1); i++) {
    h[i * 2] = h[i * 2 + 1] = h[i] + 1;
    L[i * 2] = L[i];
    R[i * 2] = (L[i] + R[i]) / 2;
    L[i * 2 + 1] = R[i * 2] + 1;
    R[i * 2 + 1] = R[i];
  }
  for (int i = (1); i <= (131072 * 2 - 1); i++) {
    a[i] = -1;
    for (int j = (L[i]); j <= (R[i]); j++) p[h[i]][j] = P[h[i]][j] = j;
    sort(p[h[i]] + L[i], p[h[i]] + R[i] + 1, cmp1);
    sort(P[h[i]] + L[i], P[h[i]] + R[i] + 1, cmp2);
  }
  for (int i = (1); i <= (131072 * 2 - 1); i++) {
    q[h[i]][L[i]] = t[p[h[i]][L[i]]];
    w[h[i]][R[i]] = g[p[h[i]][R[i]]];
    for (int j = (L[i] + 1); j <= (R[i]); j++)
      q[h[i]][j] = q[h[i]][j - 1] + t[p[h[i]][j]];
    for (int j = (R[i] - 1); j >= (L[i]); j--)
      w[h[i]][j] = w[h[i]][j + 1] + g[p[h[i]][j]];
    Q[h[i]][L[i]] = t[P[h[i]][L[i]]];
    W[h[i]][R[i]] = g[P[h[i]][R[i]]];
    e[h[i]][R[i]] = s[P[h[i]][R[i]]];
    for (int j = (L[i] + 1); j <= (R[i]); j++)
      Q[h[i]][j] = Q[h[i]][j - 1] + t[P[h[i]][j]];
    for (int j = (R[i] - 1); j >= (L[i]); j--)
      W[h[i]][j] = W[h[i]][j + 1] + g[P[h[i]][j]];
    for (int j = (R[i] - 1); j >= (L[i]); j--)
      e[h[i]][j] = e[h[i]][j + 1] + s[P[h[i]][j]];
  }
  scanf("%d", &m);
  for (int i = (1); i <= (m); i++) {
    scanf("%d%d%d", &x, &l, &r);
    printf("%I64d\n", f(1, x, l, r));
  }
}