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 RD() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
const int N = 110000, INF = ~0u >> 1;
struct Seg {
  int l, r, t, x;
  bool operator<(const Seg &a) const {
    if (l ^ a.l) return l < a.l;
    return r < a.r;
  }
};
struct Ques {
  int l, r, t, id;
  bool operator<(const Ques &x) const { return t < x.t; }
} q[10 * N];
int n, m, qcnt;
int s[N], mx[N], g[N], rk[N], tms[N];
long long ans[N];
set<Seg> st;
struct SegTree {
  int L[N << 2], R[N << 2];
  long long S[N << 2];
  void Build(int x, int l, int r) {
    L[x] = l;
    R[x] = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    Build(x << 1, l, mid);
    Build(x << 1 | 1, mid + 1, r);
    return;
  }
  void Update(int x, int p, long long v) {
    if (L[x] == R[x]) {
      S[x] = v;
      return;
    }
    int mid = (L[x] + R[x]) >> 1;
    if (p <= mid)
      Update(x << 1, p, v);
    else
      Update(x << 1 | 1, p, v);
    S[x] = S[x << 1] + S[x << 1 | 1];
    return;
  }
  long long Query(int x, int l, int r) {
    if (l <= L[x] && R[x] <= r) return S[x];
    int mid = (L[x] + R[x]) >> 1;
    long long re = 0;
    if (l <= mid) re += Query(x << 1, l, r);
    if (mid < r) re += Query(x << 1 | 1, l, r);
    return re;
  }
} T1, T2;
inline int CalcT(int t, int x, int gi, int mi) {
  return (int)min((long long)mi, x + 1ll * gi * t);
}
bool cmp(const int &x, const int &y) { return tms[x] < tms[y]; }
int main() {
  n = RD();
  for (int i = 1; i <= n; i++) {
    s[i] = RD();
    mx[i] = RD();
    g[i] = RD();
    tms[i] = g[i] ? (int)ceil(1.0 * mx[i] / g[i]) : INF;
    st.insert((Seg){i, i, 0, s[i]});
    rk[i] = i;
  }
  m = RD();
  for (int i = 1; i <= m; i++) {
    int t = RD(), l = RD(), r = RD();
    set<Seg>::iterator it = st.lower_bound((Seg){l, 0, 0, 0});
    for (; it != st.end() && it->l <= r;
         it = st.lower_bound((Seg){l, 0, 0, 0})) {
      if (it->r > r) st.insert((Seg){r + 1, it->r, it->t, it->x});
      if (it->r == it->l)
        ans[i] += CalcT(t - it->t, it->x, g[it->r], mx[it->r]);
      else
        q[++qcnt] = (Ques){max(it->l, l), min(r, it->r), t - it->t, i};
      st.erase(it);
    }
    for (; it != st.begin() && (--it)->r >= l;
         it = st.lower_bound((Seg){l, 0, 0, 0})) {
      if (it->r > r) st.insert((Seg){r + 1, it->r, it->t, it->x});
      if (it->l < l) st.insert((Seg){it->l, l - 1, it->t, it->x});
      q[++qcnt] = (Ques){max(it->l, l), min(r, it->r), t - it->t, i};
      st.erase(it);
    }
    st.insert((Seg){l, r, t, 0});
  }
  sort(rk + 1, rk + n + 1, cmp);
  sort(q + 1, q + qcnt + 1);
  T1.Build(1, 1, n);
  T2.Build(1, 1, n);
  for (int i = 1; i <= n; i++) T1.Update(1, i, g[i]);
  for (int i = 1, j = 1; i <= qcnt;) {
    if (j <= n && tms[rk[j]] <= q[i].t) {
      T1.Update(1, rk[j], 0);
      T2.Update(1, rk[j], mx[rk[j]]);
      j++;
    } else {
      ans[q[i].id] += 1ll * q[i].t * T1.Query(1, q[i].l, q[i].r) +
                      T2.Query(1, q[i].l, q[i].r);
      i++;
    }
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
  return 0;
}