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 long long N = 1e5 + 10, inf = 1e9;
struct pony {
  long long A, R, M, D;
  friend bool operator<(const pony &i, const pony &j) { return i.D < j.D; }
  pony() {}
  pony(long long _A, long long _R, long long _M) {
    A = _A, R = _R, M = _M, D = (R == 0 ? inf : (M + R - 1) / R);
  }
  pony(long long _D) : D(_D) {}
} p[N];
struct Node {
  long long t = -2;
  vector<pony> vec;
  vector<long long> Rsum, Msum;
  long long cal(long long ts) {
    long long ans = 0;
    if (t == -2)
      for (pony i : vec) ans += min(i.M, i.A + i.R * ts);
    else {
      long long x =
          upper_bound(vec.begin(), vec.end(), pony(ts - t)) - vec.begin();
      ans = Rsum[x] * (ts - t) + Msum[x];
    }
    t = ts;
    return ans;
  }
} seg[N << 2];
void Merge(long long id) {
  merge(seg[id << 1].vec.begin(), seg[id << 1].vec.end(),
        seg[id << 1 | 1].vec.begin(), seg[id << 1 | 1].vec.end(),
        back_inserter(seg[id].vec));
  seg[id].Rsum.resize(seg[id].vec.size() + 1, 0);
  seg[id].Msum.resize(seg[id].vec.size() + 1, 0);
  for (long long i = 1; i <= seg[id].vec.size(); i++)
    seg[id].Msum[i] = seg[id].Msum[i - 1] + seg[id].vec[i - 1].M;
  for (long long i = seg[id].vec.size() - 1; i >= 0; i--)
    seg[id].Rsum[i] = seg[id].Rsum[i + 1] + seg[id].vec[i].R;
}
void build(long long L, long long R, long long id = 1) {
  if (R - L == 1) {
    seg[id].vec.push_back(p[L]);
    seg[id].Rsum = {p[L].R, 0};
    seg[id].Msum = {0, p[L].M};
    return;
  }
  build(L, (L + R) >> 1, id << 1);
  build((L + R) >> 1, R, id << 1 | 1);
  Merge(id);
}
long long get(long long l, long long r, long long t, long long L, long long R,
              long long id = 1) {
  if (r <= L || R <= l) return 0;
  if (l <= L && R <= r && seg[id].t != -1) return seg[id].cal(t);
  if (seg[id].t >= 0) seg[id << 1].t = seg[id << 1 | 1].t = seg[id].t;
  long long ans = get(l, r, t, L, (L + R) >> 1, id << 1) +
                  get(l, r, t, (L + R) >> 1, R, id << 1 | 1);
  seg[id].t = (seg[id << 1].t == seg[id << 1 | 1].t ? seg[id << 1].t : -1);
  return ans;
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long A, M, R;
    cin >> A >> M >> R;
    p[i] = pony(A, R, M);
  }
  build(0, n);
  long long q;
  cin >> q;
  while (q--) {
    long long l, r, t;
    cin >> t >> l >> r;
    cout << get(l - 1, r, t, 0, n) << "\n";
  }
  return 0;
}