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;
char _;
const long long maxN = 200 * 1000 + 5;
const long long mod = 1000 * 1000 * 1000 + 7;
const long long base = 701;
const long long SQ = 500;
const long long maxL = 17;
long long s[maxN], mx[maxN], re[maxN];
vector<pair<long long, long long> > pos[maxN], neg[maxN];
long long fen1[maxN], fen2[maxN], ans[maxN];
void add1(long long n, long long k) {
  for (; n > 0; n -= n & (-n)) fen1[n] += k;
}
long long get1(long long n) {
  long long res = 0;
  for (; n < maxN; n += n & (-n)) res += fen1[n];
  return res;
}
void add2(long long n, long long k) {
  for (; n > 0; n -= n & (-n)) fen2[n] += k;
}
long long get2(long long n) {
  long long res = 0;
  for (; n < maxN; n += n & (-n)) res += fen2[n];
  return res;
}
long long upd(long long x) {
  if (x > maxN - 5) return get2(maxN - 5);
  return get2(x) + get1(x) * x;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> s[i] >> mx[i] >> re[i];
  long long m;
  cin >> m;
  for (long long i = 0; i < m; i++) {
    long long t, l, r;
    cin >> t >> l >> r;
    l--;
    r--;
    pos[l].push_back({t, i});
    neg[r].push_back({t, i});
  }
  set<pair<long long, long long> > ss;
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < (long long)pos[i].size(); j++) {
      auto it = ss.lower_bound(pos[i][j]);
      if (it != ss.end()) {
        auto xx = *it;
        if (it != ss.begin()) {
          it--;
          auto yy = *it;
          ans[xx.second] += upd(xx.first - yy.first);
        }
        ans[xx.second] -= upd(xx.first - pos[i][j].first);
      }
      it = ss.lower_bound(pos[i][j]);
      if (it != ss.begin()) {
        it--;
        auto yy = *it;
        ans[pos[i][j].second] -= upd(pos[i][j].first - yy.first);
      }
      ss.insert(pos[i][j]);
    }
    if (mx[i]) {
      if (ss.size()) {
        long long tmp = s[i] + (1LL) * ss.begin()->first * re[i];
        tmp = min(tmp, (1LL) * mx[i]);
        ans[ss.begin()->second] += tmp;
      }
      if (re[i]) {
        long long df = (mx[i] - 1) / re[i];
        add1(df, re[i]);
        add2(maxN - 2, mx[i]);
        add2(df, -mx[i]);
      }
    }
    for (long long j = 0; j < (long long)neg[i].size(); j++) {
      ss.erase(neg[i][j]);
      auto it = ss.lower_bound(neg[i][j]);
      if (it != ss.begin()) {
        it--;
        auto yy = *it;
        ans[neg[i][j].second] += upd(neg[i][j].first - yy.first);
      }
      it = ss.lower_bound(neg[i][j]);
      if (it != ss.end()) {
        auto xx = *it;
        ans[xx.second] += upd(xx.first - neg[i][j].first);
        if (it != ss.begin()) {
          it--;
          auto yy = *it;
          ans[xx.second] -= upd(xx.first - yy.first);
        }
      }
    }
  }
  for (long long i = 0; i < m; i++) cout << ans[i] << endl;
  return 0;
}