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 long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const long long maxn = 2e5 + 1e2;
long long su[maxn];
long long m[maxn];
long long r[maxn];
long long n, q;
vector<long long> v;
long long val[maxn];
long long sz;
long long tot;
struct Node {
  long long l, r, tag, tim;
};
set<Node> s;
bool operator<(Node a, Node b) { return a.l < b.l; }
struct pp {
  long long l, r, val, sum;
};
pp t[maxn * 20];
void up(long long root) {
  t[root].val = t[t[root].l].val + t[t[root].r].val;
  t[root].sum = t[t[root].l].sum + t[t[root].r].sum;
}
long long modify(long long pre, long long l, long long r, long long x,
                 long long y, long long z) {
  long long now = ++tot;
  if (l == r) {
    t[now].val = t[pre].val + z;
    t[now].sum = t[pre].sum + y;
    return now;
  }
  long long mid = l + r >> 1;
  if (x <= mid) {
    t[now].r = t[pre].r;
    t[now].l = modify(t[pre].l, l, mid, x, y, z);
  } else {
    t[now].l = t[pre].l;
    t[now].r = modify(t[pre].r, mid + 1, r, x, y, z);
  }
  up(now);
  return now;
}
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  pair<long long, long long> c;
  c.first = a.first + b.first;
  c.second = a.second + b.second;
  return c;
}
pair<long long, long long> query(long long root1, long long root2, long long l,
                                 long long r, long long x, long long y) {
  if (x <= l && r <= y)
    return make_pair(t[root2].val - t[root1].val, t[root2].sum - t[root1].sum);
  long long mid = l + r >> 1;
  pair<long long, long long> ans;
  ans.first = 0;
  ans.second = 0;
  if (x <= mid) ans = ans + query(t[root1].l, t[root2].l, l, mid, x, y);
  if (y > mid) ans = ans + query(t[root1].r, t[root2].r, mid + 1, r, x, y);
  return ans;
}
long long root[maxn];
Node a[maxn];
long long cnt;
long long count(long long l, long long r, long long t) {
  pair<long long, long long> now, now1;
  long long tt = t;
  t = upper_bound(v.begin(), v.end(), t) - v.begin();
  if (t != 0) now = query(root[l - 1], root[r], 1, sz, 1, t);
  now1 = query(root[l - 1], root[r], 1, sz, t + 1, sz);
  return now.first + now1.second * tt;
}
long long lyf[maxn];
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++)
    su[i] = read(), m[i] = read(), r[i] = read();
  for (long long i = 1; i <= n; i++) lyf[i] = r[i];
  for (long long i = 1; i <= n; i++)
    if (r[i] != 0)
      val[i] = (m[i] - 1) / r[i] + 1;
    else
      val[i] = 1e10;
  for (long long i = 1; i <= n; i++) v.push_back(val[i]);
  sort(v.begin(), v.end());
  sz = unique(v.begin(), v.end()) - v.begin();
  v.resize(sz);
  for (long long i = 1; i <= n; i++)
    val[i] = lower_bound(v.begin(), v.end(), val[i]) - v.begin() + 1;
  for (long long i = 1; i <= n; i++)
    root[i] = modify(root[i - 1], 1, sz, val[i], r[i], m[i]);
  for (long long i = 1; i <= n; i++) s.insert((Node){i, i, su[i], 0});
  q = read();
  for (long long i = 1; i <= q; i++) {
    long long t = read(), l = read(), r = read();
    cnt = 0;
    set<Node>::iterator it, it1;
    it = s.upper_bound((Node){l, r, 0, t});
    it--;
    it1 = it;
    while (it != s.end()) {
      if ((*it).l > r) break;
      a[++cnt] = *it;
      it++;
    }
    for (long long j = 1; j <= cnt; j++)
      s.erase(s.find((Node){a[j].l, a[j].r, a[j].tag, a[j].tim}));
    if (a[1].l != l) s.insert((Node){a[1].l, l - 1, 0, a[1].tim}), a[1].l = l;
    if (a[cnt].r != r)
      s.insert((Node){r + 1, a[cnt].r, 0, a[cnt].tim}), a[cnt].r = r;
    s.insert((Node){l, r, 0, t});
    long long ans = 0;
    for (long long j = 1; j <= cnt; j++) {
      if (a[j].tim != 0)
        ans = ans + count(a[j].l, a[j].r, t - a[j].tim);
      else {
        long long now = a[j].l;
        ans = ans + min(m[now], su[now] + lyf[now] * t);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}