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 const MAX = 1e5 + 41;
int n;
int q;
int s[MAX];
int m[MAX];
int r[MAX];
int const BLOCK = 666;
bool sp[MAX];
int lt[MAX];
int ltb[MAX];
vector<pair<int, int> > a[MAX];
vector<long long> prefsum[MAX];
vector<long long> prefspeed[MAX];
int const INF = 2e9 + 41;
void init() {
  for (int i = 0, k = 0; i < n; i += BLOCK, k++) {
    for (int j = 0; j <= BLOCK - 1; j++) {
      if (i + j >= n) break;
      int m = ::m[i + j];
      int r = ::r[i + j];
      if (r != 0) {
        a[k].push_back(make_pair((m + r - 1) / r, i + j));
      } else {
        a[k].push_back(make_pair(INF, i + j));
      }
    }
    sort(a[k].begin(), a[k].end());
    long long sm = 0;
    long long sr = 0;
    for (int j = 0; j <= (int)a[k].size() - 1; j++) {
      int m = ::m[a[k][j].second];
      int r = ::r[a[k][j].second];
      sm += m;
      sr += r;
      prefsum[k].push_back(sm);
      prefspeed[k].push_back(sr);
    }
  }
}
long long queryblock(int id, int t) {
  long long res = 0;
  int p = (int)(lower_bound(a[id].begin(), a[id].end(),
                            make_pair(t - ltb[id], INF)) -
                a[id].begin());
  p--;
  if (p >= 0) {
    res += prefsum[id][p];
  }
  res += prefspeed[id].back() * (t - ltb[id]);
  if (p >= 0) {
    res -= prefspeed[id][p] * (t - ltb[id]);
  }
  ltb[id] = t;
  return res;
}
long long bruteblock(int id, int l, int r, int t) {
  if (l > r) return 0LL;
  l -= BLOCK * id;
  r -= BLOCK * id;
  sp[id] = false;
  int sh = id * BLOCK;
  for (int i = 0; i <= (int)a[id].size() - 1; i++) {
    lt[sh + i] = max(lt[sh + i], ltb[id]);
  }
  long long res = 0;
  for (int i = l; i <= r; i++) {
    long long add = min((long long)m[sh + i],
                        (long long)::r[sh + i] * (t - lt[sh + i]) + s[sh + i]);
    res += add;
    lt[sh + i] = t;
    s[sh + i] = 0;
  }
  return res;
}
int getblockright(int x) {
  int res = (x / BLOCK + 1) * BLOCK - 1;
  res = min(res, n - 1);
  return res;
}
int getblockleft(int x) { return x / BLOCK * BLOCK; }
void solve() {
  init();
  scanf("%d", &q);
  for (int o = 1; o <= q; o++) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    l--;
    r--;
    long long res = 0;
    int rl = min(r, getblockright(l));
    res += bruteblock(l / BLOCK, l, rl, t);
    l = rl + 1;
    int lr = max(l, getblockleft(r));
    res += bruteblock(r / BLOCK, lr, r, t);
    r = lr;
    while (l < r) {
      if (sp[l / BLOCK]) {
        res += queryblock(l / BLOCK, t);
      } else {
        res += bruteblock(l / BLOCK, l, l + BLOCK - 1, t);
        sp[l / BLOCK] = 1;
        ltb[l / BLOCK] = t;
      }
      l += BLOCK;
    }
    printf("%lld\n", res);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i <= n - 1; i++) {
    scanf("%d %d %d", &s[i], &m[i], &r[i]);
  }
  solve();
  return 0;
}