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;
const int maxn = 100005;
int n, m, len[maxn << 2];
bool first[maxn << 2];
long long mm[maxn], rr[maxn], ss[maxn], last[maxn << 2];
vector<long long> summ[maxn << 2], sumr[maxn << 2];
vector<int> tree[maxn << 2];
bool cmp(int a, int b) { return mm[a] * rr[b] < mm[b] * rr[a]; }
void build(int cur, int l, int r) {
  len[cur] = 0;
  first[cur] = true, last[cur] = -1;
  tree[cur].clear();
  tree[cur].push_back(0);
  for (int i = l; i <= r; i++)
    if (mm[i] != 0 && rr[i] != 0) tree[cur].push_back(i), len[cur]++;
  sort(tree[cur].begin() + 1, tree[cur].end(), cmp);
  summ[cur].clear();
  sumr[cur].clear();
  summ[cur].push_back(0);
  sumr[cur].push_back(0);
  long long sr = 0, sm = 0;
  for (int i = 1; i <= len[cur]; i++) {
    sr += rr[tree[cur][i]];
    sm += mm[tree[cur][i]];
    sumr[cur].push_back(sr);
    summ[cur].push_back(sm);
  }
  if (l != r) {
    build((cur << 1), l, ((l + r) >> 1));
    build((cur << 1 | 1), ((l + r) >> 1) + 1, r);
  }
}
int find(int cur, long long t) {
  int l = 1, r = len[cur];
  while (l <= r) {
    if (t * rr[tree[cur][((l + r) >> 1)]] >= mm[tree[cur][((l + r) >> 1)]])
      l = ((l + r) >> 1) + 1;
    else
      r = ((l + r) >> 1) - 1;
  }
  return l - 1;
}
long long ask(int cur, int l, int r, long long t) {
  if (l == r && first[cur]) {
    long long ret = min(mm[l], t * rr[l] + ss[l]);
    ss[l] = 0, first[cur] = false;
    return ret;
  }
  if (last[cur] != -1) {
    long long delta = t - last[cur];
    int mid = find(cur, delta);
    long long ret = 0;
    ret += summ[cur][mid];
    ret += (sumr[cur][len[cur]] - sumr[cur][mid]) * delta;
    return ret;
  }
  long long ret = 0;
  ret += ask((cur << 1), l, ((l + r) >> 1), t);
  ret += ask((cur << 1 | 1), ((l + r) >> 1) + 1, r, t);
  return ret;
}
void down(int cur) {
  if (last[cur] != -1) {
    first[(cur << 1)] = first[(cur << 1 | 1)] = false;
    last[(cur << 1)] = last[(cur << 1 | 1)] = last[cur];
    last[cur] = -1;
  }
}
long long query(int cur, int l, int r, int ql, int qr, long long t) {
  if (ql <= l && r <= qr) {
    long long ret = ask(cur, l, r, t);
    first[cur] = false, last[cur] = t;
    return ret;
  }
  down(cur);
  long long ret = 0;
  if (ql <= ((l + r) >> 1))
    ret += query((cur << 1), l, ((l + r) >> 1), ql, qr, t);
  if (qr > ((l + r) >> 1))
    ret += query((cur << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, t);
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%I64d%I64d%I64d", &ss[i], &mm[i], &rr[i]);
  build(1, 1, n);
  scanf("%d", &m);
  int qq = 0;
  while (m--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    printf("%I64d\n", query(1, 1, n, l, r, t));
  }
  return 0;
}