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;
inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}
constexpr int N = 1e5 + 7;
constexpr long long inf = 1e18 + 7;
int n;
struct node {
  vector<pair<int, pair<long long, long long> > > v;
  int last, pre;
  node() {
    last = -1, pre = 0;
    v.clear();
  }
} a[4 * N];
struct pony {
  int s, mx, r;
} pon[N];
int saghf(int x, int y) {
  if (y == 0) return int(1e9 + 77);
  if (x % y == 0) return x / y;
  return x / y + 1;
}
void Sort(int tag) {
  sort(a[tag].v.begin(), a[tag].v.end());
  for (int i = 1; i < ((int)a[tag].v.size()); i++)
    a[tag].v[i].second.first += a[tag].v[i - 1].second.first;
  for (int i = ((int)a[tag].v.size()) - 2; i >= 0; --i)
    a[tag].v[i].second.second += a[tag].v[i + 1].second.second;
}
void build(int tag = 1, int s = 0, int e = n) {
  if (e - s == 1) {
    a[tag].last = 0;
    a[tag].v.push_back({saghf(pon[s].mx, pon[s].r), {pon[s].mx, pon[s].r}});
    a[tag].pre = pon[s].s;
    return;
  }
  int mid = (s + e) / 2;
  build(tag * 2, s, mid);
  build(tag * 2 + 1, mid, e);
  for (auto i : a[tag * 2].v) a[tag].v.push_back(i);
  for (auto i : a[tag * 2 + 1].v) a[tag].v.push_back(i);
  Sort(tag * 2);
  Sort(tag * 2 + 1);
  if (tag == 1) Sort(tag);
}
long long query(int l, int r, int t, int tag = 1, int s = 0, int e = n) {
  if (l >= e || r <= s) return 0;
  if (s >= l && e <= r && a[tag].last != -1) {
    if (e - s == 1) {
      long long ans =
          min(a[tag].pre + a[tag].v[0].second.second * 1ll * (t - a[tag].last),
              a[tag].v[0].second.first);
      a[tag].last = t, a[tag].pre = 0;
      return ans;
    } else {
      long long ans;
      int pos = upper_bound(a[tag].v.begin(), a[tag].v.end(),
                            make_pair(t - a[tag].last, make_pair(inf, inf))) -
                a[tag].v.begin();
      if (pos == ((int)a[tag].v.size()))
        ans = a[tag].v[pos - 1].second.first;
      else if (pos == 0)
        ans = a[tag].v[pos].second.second * 1ll * (t - a[tag].last);
      else
        ans = a[tag].v[pos].second.second * 1ll * (t - a[tag].last) +
              a[tag].v[pos - 1].second.first;
      a[tag].last = t;
      return ans;
    }
  }
  a[tag * 2].last = max(a[tag * 2].last, a[tag].last);
  a[tag * 2 + 1].last = max(a[tag * 2 + 1].last, a[tag].last);
  int mid = (s + e) / 2;
  long long ans =
      query(l, r, t, tag * 2, s, mid) + query(l, r, t, tag * 2 + 1, mid, e);
  if (a[tag * 2].last == a[tag * 2 + 1].last)
    a[tag].last = a[tag * 2].last;
  else
    a[tag].last = -1;
  return ans;
}
int32_t main() {
  n = in();
  for (int i = 0; i < n; i++)
    pon[i].s = in(), pon[i].mx = in(), pon[i].r = in();
  build();
  int Q = in();
  while (Q--) {
    int t = in(), l = in() - 1, r = in();
    cout << query(l, r, t) << endl;
  }
}