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 inf = 1e9 + 5;
const long long linf = 1e18 + 5;
const int N = 1e5 + 5;
const int K = 1000;
const int T = N / K + 5;
int n, q, st[N], ma[N], re[N], b[T], e[T], last[T], lasti[N], rtime[N],
    _time[N], suml[N], sumr[N];
bool is_zero[T];
int query(int x, int t, int l, int r) {
  if (r < b[x] or l > e[x]) return 0;
  if (l <= b[x] and e[x] <= r and is_zero[x]) {
    int dif = t - last[x];
    last[x] = t;
    int ind = lower_bound(_time + b[x], _time + e[x] + 1, dif) - _time;
    int ans = 0;
    if (ind <= e[x]) ans += sumr[ind] * dif;
    if (ind - 1 >= b[x]) ans += suml[ind - 1];
    return ans;
  }
  int ans = 0;
  l = max(l, b[x]);
  r = min(r, e[x]);
  for (int i = l; i <= r; i++) {
    ans += min((long long)ma[i],
               st[i] + (long long)(t - max(last[x], lasti[i])) * re[i]);
    lasti[i] = t;
    st[i] = 0;
  }
  is_zero[x] = l <= b[x] and e[x] <= r;
  if (is_zero[x]) last[x] = t;
  return ans;
}
int main() {
  ios ::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> st[i] >> ma[i] >> re[i];
  for (int i = 1; (i - 1) * K + 1 <= n; i++) {
    b[i] = (i - 1) * K + 1;
    e[i] = min(i * K, n);
    for (int j = b[i]; j <= e[i]; j++) {
      rtime[j] = re[j] ? ma[j] / re[j] : inf;
      _time[j] = rtime[j];
    }
    sort(_time + b[i], _time + e[i] + 1);
    for (int j = b[i]; j <= e[i]; j++) {
      int ind = lower_bound(_time + b[i], _time + e[i] + 1, rtime[j]) - _time;
      suml[ind] += ma[j];
      sumr[ind] += re[j];
    }
    for (int j = e[i] - 1; j >= b[i]; j--) sumr[j] += sumr[j + 1];
    for (int j = b[i] + 1; j <= e[i]; j++) suml[j] += suml[j - 1];
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    long long ans = 0;
    for (int i = 1; (i - 1) * K + 1 <= n; i++) ans += query(i, t, l, r);
    cout << ans << '\n';
  }
  return 0;
}