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;
struct sTree {
  int L, R;
  int pl, pr;
  long long sum_m;
  long long sum_r;
} tree[2000000];
int treeSize;
int s[100009];
int r[100009];
int m[100009];
int BuildTree(int L, int R) {
  int cur = treeSize++;
  tree[cur].L = L;
  tree[cur].R = R;
  tree[cur].sum_r = r[L];
  if (L < R) {
    tree[cur].pl = BuildTree(L, (L + R) / 2);
    tree[cur].pr = BuildTree((L + R) / 2 + 1, R);
    tree[cur].sum_r = tree[tree[cur].pl].sum_r + tree[tree[cur].pr].sum_r;
  }
  return cur;
}
int Toggle(int i, int cur) {
  tree[treeSize] = tree[cur];
  cur = treeSize;
  treeSize++;
  if (tree[cur].L == tree[cur].R) {
    tree[cur].sum_m = m[i];
    tree[cur].sum_r = 0;
    return cur;
  }
  if (i <= tree[tree[cur].pl].R)
    tree[cur].pl = Toggle(i, tree[cur].pl);
  else
    tree[cur].pr = Toggle(i, tree[cur].pr);
  tree[cur].sum_m = tree[tree[cur].pl].sum_m + tree[tree[cur].pr].sum_m;
  tree[cur].sum_r = tree[tree[cur].pl].sum_r + tree[tree[cur].pr].sum_r;
  return cur;
}
pair<long long, long long> Get(int L, int R, int cur) {
  if (L <= tree[cur].L && R >= tree[cur].R) {
    return make_pair(tree[cur].sum_m, tree[cur].sum_r);
  }
  pair<long long, long long> ans = make_pair(0, 0);
  if (L <= tree[tree[cur].pl].R && tree[tree[cur].pl].L <= R) {
    pair<long long, long long> tmp = Get(L, R, tree[cur].pl);
    ans.first += tmp.first;
    ans.second += tmp.second;
  }
  if (L <= tree[tree[cur].pr].R && tree[tree[cur].pr].L <= R) {
    pair<long long, long long> tmp = Get(L, R, tree[cur].pr);
    ans.first += tmp.first;
    ans.second += tmp.second;
  }
  return ans;
}
int roots[100001];
long long Calc(int L, int R, int time) {
  if (L == R) {
    return min((long long)m[L], s[L] + (long long)time * r[L]);
  }
  pair<long long, long long> tmp = Get(L, R, roots[time]);
  return tmp.first + (long long)time * tmp.second;
}
vector<int> ind[100001];
int n;
int fwt[100001];
int fwt_sum(int k) {
  int ans = 0;
  while (k) {
    ans += fwt[k];
    k -= k & (-k);
  }
  return ans;
}
void fwt_add(int k, int d) {
  while (k <= n) {
    fwt[k] += d;
    k += k & (-k);
  }
}
int fwt_getKth(int k) {
  int ans = 0;
  for (int i = 18; i >= 0; i--) {
    if (ans + (1 << i) <= n && fwt[ans + (1 << i)] < k) {
      ans += (1 << i);
      k -= fwt[ans];
    }
  }
  return ans + 1;
}
int lastTime[100001];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d %d", &s[i], &m[i], &r[i]);
    if (m[i] == 0) r[i] = 0;
    if (r[i]) {
      ind[m[i] / r[i] + 1].push_back(i);
    }
  }
  roots[0] = BuildTree(1, n);
  for (int k = 1; k <= 100000; k++) {
    roots[k] = roots[k - 1];
    for (int i = 0; i < ind[k].size(); i++)
      roots[k] = Toggle(ind[k][i], roots[k]);
  }
  for (int k = 1; k <= n; k++) {
    fwt_add(k, 1);
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int time, L, R;
    scanf("%d %d %d", &time, &L, &R);
    long long ans = 0;
    int last, ind = L;
    while (ind <= R) {
      int cur = fwt_sum(ind);
      int next = fwt_getKth(cur + 1) - 1;
      cur = fwt_getKth(cur);
      ans += Calc(ind, min(R, next), min(time - lastTime[cur], 100000));
      s[cur] = 0;
      if (cur >= L) fwt_add(cur, -1);
      last = lastTime[cur];
      ind = next + 1;
    }
    printf("%I64d\n", ans);
    fwt_add(L, 1);
    lastTime[L] = time;
    if (R + 1 <= n && fwt_sum(R + 1) == fwt_sum(R)) {
      lastTime[R + 1] = last;
      fwt_add(R + 1, 1);
    }
  }
}