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 N = 100005;
const int M = 10000005;
struct node {
  int l, r, T;
  bool operator<(const node &a) const { return l == a.l ? r < a.r : l < a.l; }
};
set<node> S;
int n, Q, x[N], y[N], z[N];
int rt1[N], rt2[N], nd;
int ls[M], rs[M];
long long t[M];
void insert(int &nk, int k, int l, int r, int p, int v) {
  nk = ++nd;
  t[nk] = t[k] + v;
  ls[nk] = ls[k];
  rs[nk] = rs[k];
  if (l == r) return;
  int mid = (l + r) / 2;
  if (p <= mid)
    insert(ls[nk], ls[k], l, mid, p, v);
  else
    insert(rs[nk], rs[k], mid + 1, r, p, v);
}
long long ask(int k, int l, int r, int x, int y) {
  if (!k || (l == x && r == y)) return t[k];
  int mid = (l + r) / 2;
  if (y <= mid) return ask(ls[k], l, mid, x, y);
  if (x > mid) return ask(rs[k], mid + 1, r, x, y);
  return ask(ls[k], l, mid, x, mid) + ask(rs[k], mid + 1, r, mid + 1, y);
}
void split(int x) {
  set<node>::iterator it;
  it = S.lower_bound((node){x, 0, 0});
  if (it != S.end() && it->l == x) return;
  assert(it != S.begin());
  it--;
  node tmp = *it;
  S.erase(it);
  S.insert((node){tmp.l, x - 1, tmp.T});
  S.insert((node){x, tmp.r, tmp.T});
}
long long query(node tmp, int T) {
  long long ans = 0;
  if (tmp.T == -1)
    for (int i = (int)(tmp.l); i <= (int)(tmp.r); i++)
      ans += min(1ll * y[i], x[i] + 1ll * T * z[i]);
  else {
    int dif = min(N - 1, T - tmp.T);
    ans += 1ll * dif *
           (ask(rt1[tmp.r], 0, N, dif, N) - ask(rt1[tmp.l - 1], 0, N, dif, N));
    ans += ask(rt2[tmp.r], 0, N, 0, dif) - ask(rt2[tmp.l - 1], 0, N, 0, dif);
  }
  S.insert((node){n + 1, n + 1, -1});
  return ans;
}
long long ask(int l, int r, int T) {
  set<node>::iterator it;
  it = S.lower_bound((node){l, 0, 0});
  long long ans = 0;
  for (; it != S.end() && it->r <= r; S.erase(it++)) ans += query(*it, T);
  S.insert((node){l, r, T});
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) {
    scanf("%d%d%d", &x[i], &y[i], &z[i]);
    rt1[i] = rt1[i - 1];
    rt2[i] = rt2[i - 1];
    if (!z[i]) continue;
    int clk = y[i] / z[i];
    insert(rt1[i], rt1[i], 0, N, clk, z[i]);
    insert(rt2[i], rt2[i], 0, N, clk + 1, y[i]);
  }
  S.insert((node){n + 1, n + 1, -1});
  S.insert((node){1, n, -1});
  scanf("%d", &Q);
  while (Q--) {
    int l, r, t;
    scanf("%d%d%d", &t, &l, &r);
    split(l);
    split(r + 1);
    printf("%lld\n", ask(l, r, t));
  }
}