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>
#pragma comment(linker, "/STACK:1000000000")
using namespace std;
const bool db = false;
vector<pair<int, int> > t[4 * 100010];
vector<long long> suff[4 * 100010], pref[4 * 100010];
int last[4 * 100010];
int n, q;
int S[100010], M[100010], RN[100010];
int I[100010], T, X, Y;
void build(int v, int l, int r) {
  suff[v].resize(r - l + 1);
  pref[v].resize(r - l + 1);
  t[v].resize(r - l + 1);
  if (l != r) {
    int m = (l + r) / 2;
    build(v + v, l, m);
    build(v + v + 1, m + 1, r);
    merge(t[v + v].begin(), t[v + v].end(), t[v + v + 1].begin(),
          t[v + v + 1].end(), t[v].begin());
  } else {
    t[v][0] = make_pair(I[l], l);
  }
  pref[v][0] = M[t[v][0].second];
  suff[v][0] = RN[t[v][0].second];
  for (int i = 1; i < t[v].size(); ++i) {
    pref[v][i] = pref[v][i - 1] + M[t[v][i].second];
    suff[v][i] = suff[v][i - 1] + RN[t[v][i].second];
  }
}
long long go(int v, int l, int r, int dat) {
  dat -= last[v];
  last[v] += dat;
  int it = upper_bound(t[v].begin(), t[v].end(), make_pair(dat, 1000000007)) -
           t[v].begin();
  if (it == t[v].size()) {
    return pref[v].back();
  }
  if (it == 0) {
    return suff[v].back() * 1LL * dat;
  }
  return pref[v][it - 1] + (suff[v][r - l] - suff[v][it - 1]) * 1LL * dat;
}
long long query(int v, int L, int R, int l, int r, int dat) {
  if (l > R || r < L) return 0LL;
  if (l <= L && R <= r && last[v]) return go(v, L, R, dat);
  if (L == R) {
    last[v] = dat;
    return min(0LL + M[t[v][0].second],
               S[t[v][0].second] + dat * 1LL * RN[t[v][0].second]);
  }
  int M = (L + R) >> 1;
  last[v + v] = max(last[v], last[v + v]);
  last[v + v + 1] = max(last[v + v + 1], last[v]);
  if (l <= L && R <= r)
    last[v] = dat;
  else
    last[v] = 0;
  return query(v + v, L, M, l, r, dat) + query(v + v + 1, M + 1, R, l, r, dat);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &S[i], &M[i], &RN[i]);
    if (RN[i] == 0) {
      I[i] = 1000000007;
      continue;
    }
    I[i] = (M[i] + RN[i] - 1) / RN[i];
  }
  build(1, 1, n);
  scanf("%d", &q);
  while (q-- > 0) {
    scanf("%d%d%d", &T, &X, &Y);
    printf("%lld\n", query(1, 1, n, X, Y, T));
  }
  getchar();
  getchar();
  return 0;
}