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;
template <typename T>
inline T sqr(T x) {
  return x * x;
}
template <typename T>
inline T getNext() {
  T s = 1, x = 0, c = getc(stdin);
  while (c <= 32) c = getc(stdin);
  if (c == '-') s = -1, c = getc(stdin);
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getc(stdin);
  return x * s;
}
const int MaxN = int(1e5);
const int K = 18;
const int MaxT = int((1 << K));
int s[MaxN], m[MaxN], rg[MaxN];
bool good[MaxT];
int last[MaxT], tmax[K][MaxT], tmp[K][MaxT];
long long summax[K][MaxT], sumreg[K][MaxT];
int mydiv(int i, int j) { return j ? (i + j - 1) / j : INT_MAX; }
bool cmp(int i, int j) { return mydiv(m[i], rg[i]) < mydiv(m[j], rg[j]); }
void build(int l = 0, int r = MaxT >> 1, int d = 0) {
  if (l + 1 == r) {
    tmp[d][l] = l;
    tmax[d][l] = mydiv(m[l], rg[l]);
    summax[d][l] = m[l];
    sumreg[d][l] = rg[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, d + 1);
  build(m, r, d + 1);
  merge(tmp[d + 1] + l, tmp[d + 1] + m, tmp[d + 1] + m, tmp[d + 1] + r,
        tmp[d] + l, *cmp);
  for (int i = l; i < r; i++) {
    tmax[d][i] = mydiv(::m[tmp[d][i]], rg[tmp[d][i]]);
    summax[d][i] = ::m[tmp[d][i]];
    sumreg[d][i] = rg[tmp[d][i]];
  }
  for (int i = l + 1; i != r + 1; i += 1) summax[d][i] += summax[d][i - 1];
  for (int i = r - 1; i != l - 1; i += -1) sumreg[d][i] += sumreg[d][i + 1];
}
long long query(int t, int l, int r, int nl = 0, int nr = 1 << 17, int k = 0,
                int d = 0) {
  if (l <= nl && nr <= r && good[k]) {
    int p = upper_bound(tmax[d] + nl, tmax[d] + nr, t - last[k]) - tmax[d];
    long long a = p == nl ? 0 : summax[d][p - 1];
    long long b = p == nr ? 0 : sumreg[d][p] * (t - last[k]);
    last[k] = t;
    return a + b;
  }
  if (r <= nl || nr <= l) return 0;
  if (nl + 1 == nr) {
    long long a = min(1ll * m[nl], s[nl] + 1ll * rg[nl] * (t - last[k]));
    s[nl] = 0;
    good[k] = true;
    last[k] = t;
    return a;
  }
  if (good[k]) {
    good[k] = false;
    good[k + k + 1] = true;
    last[k + k + 1] = last[k];
    good[k + k + 2] = true;
    last[k + k + 2] = last[k];
  }
  int nm = (nl + nr) / 2;
  long long a = query(t, l, r, nl, nm, k + k + 1, d + 1);
  long long b = query(t, l, r, nm, nr, k + k + 2, d + 1);
  good[k] = (l <= nl && nr <= r);
  last[k] = t;
  return a + b;
}
int main() {
  int n = getNext<int>();
  for (int i = 0; i != n; i += 1)
    s[i] = getNext<int>(), m[i] = getNext<int>(), rg[i] = getNext<int>();
  build();
  int q = getNext<int>();
  while (q--) {
    int t = getNext<int>(), l = getNext<int>() - 1, r = getNext<int>();
    printf("%I64d\n", query(t, l, r));
  }
  return 0;
}