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;
struct unit {
  long long t, v, m;
  unit(int _t, int _v, int _m) : t(_t), v(_v), m(_m) {}
  bool operator<(const unit &cmp) const { return t < cmp.t; }
};
long long init[100000], v[100000], up[100000];
int n, m;
struct seg {
  int l, r, cur;
  seg *lt, *rt;
  vector<unit> p;
  seg(int _l, int _r) : l(_l), r(_r), cur(-1), lt(NULL), rt(NULL) {
    for (int i = l; i < r; i++)
      p.push_back(unit(v[i] ? up[i] / v[i] : 1000000, v[i], up[i]));
    sort(p.begin(), p.end());
    for (int i = 1; i < r - l; i++) p[i].m += p[i - 1].m;
    for (int i = r - l - 2; i >= 0; i--) p[i].v += p[i + 1].v;
    if (r - l > 1) {
      int mid = (r + l) >> 1;
      lt = new seg(l, mid);
      rt = new seg(mid, r);
    }
  }
  long long query(int ll, int rr, int now) {
    if (ll <= l && rr >= r && cur > -2) {
      long long res = 0;
      if (cur == -1) {
        for (int i = l; i < r; i++) res += min(up[i], init[i] + v[i] * now);
      } else {
        int d = now - cur;
        if (d <= p[0].t)
          res = p[0].v * d;
        else if (d > p.back().t)
          res = p.back().m;
        else {
          auto x = lower_bound(p.begin(), p.end(), unit(d, -1, -1));
          res = x->v * d + (--x)->m;
        }
      }
      cur = now;
      return res;
    } else {
      long long res = 0;
      if (cur >= 0) lt->cur = rt->cur = cur;
      int mid = (l + r) >> 1;
      if (ll < mid) res += lt->query(ll, rr, now);
      if (rr > mid) res += rt->query(ll, rr, now);
      if (ll <= l && r <= rr)
        cur = now;
      else if (lt->cur == rt->cur)
        cur = lt->cur;
      else
        cur = -2;
      return res;
    }
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> init[i] >> up[i] >> v[i];
  seg T(0, n);
  cin >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    cout << T.query(b - 1, c, a) << endl;
  }
  return 0;
}