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 node {
  int l, r, t;
  node() {}
  node(int l1, int r1, int t1) : l(l1), r(r1), t(t1) {}
};
inline bool operator<(const node &x, const node &y) { return x.l < y.l; }
struct hhhh {
  int l, r, t, id;
} h[500010];
set<node> st;
long long S[100010], M[100010], R[100010], ans[100010], c[100010];
int g[100010], n, m, tt;
inline int rd() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void print(long long x) {
  static char s[233];
  if (!x) {
    putchar('0');
    putchar('\n');
    return;
  }
  int tot = 0;
  for (; x; x /= 10) s[++tot] = x % 10 + '0';
  for (; tot; tot--) putchar(s[tot]);
  putchar('\n');
}
inline long long min(const long long &x, const long long &y) {
  return (x < y) ? x : y;
}
inline long long max(const long long &x, const long long &y) {
  return (x > y) ? x : y;
}
inline set<node>::iterator split(int x) {
  set<node>::iterator it = st.upper_bound(node(x, 0, 0));
  it--;
  if (x == (*it).l) return it;
  node hh = *it;
  st.erase(hh);
  st.insert(node(hh.l, x - 1, hh.t));
  return st.insert(node(x, hh.r, hh.t)).first;
}
inline void pre_gao(int l, int r, int t, int id) {
  for (int i = l; i <= r; i++) ans[id] += min(S[i] + R[i] * t, M[i]);
}
inline bool cmp(const hhhh &x, const hhhh &y) { return x.t < y.t; }
inline bool cmp1(const int &x, const int &y) {
  if (!R[x]) return false;
  if (!R[y]) return true;
  return (M[x] / R[x] + 1) < (M[y] / R[y] + 1);
}
long long sum[400010], s[400010], tag[400010];
inline void gao(const int &o, const long long &hh) {
  sum[o] += s[o] * hh;
  tag[o] += hh;
}
inline void pushdown(const int &o) {
  if (!tag[o]) return;
  gao(o << 1, tag[o]);
  gao(o << 1 | 1, tag[o]);
  tag[o] = 0;
}
inline void build(int o, int l, int r) {
  sum[o] = tag[o] = 0;
  if (l == r) {
    s[o] = R[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  s[o] = s[o << 1] + s[o << 1 | 1];
}
inline void del(int o, int l, int r, int x) {
  if (l == r) {
    s[o] = sum[o] = 0;
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  if (x <= mid)
    del(o << 1, l, mid, x);
  else
    del(o << 1 | 1, mid + 1, r, x);
  sum[o] = sum[o << 1] + sum[o << 1 | 1];
  s[o] = s[o << 1] + s[o << 1 | 1];
}
inline long long query(int o, int l, int r, int x, int y) {
  if (l >= x && r <= y) return sum[o];
  pushdown(o);
  int mid = (l + r) >> 1;
  long long res = 0;
  if (x <= mid) res += query(o << 1, l, mid, x, y);
  if (y > mid) res += query(o << 1 | 1, mid + 1, r, x, y);
  return res;
}
inline void add(int x, long long y) {
  for (; x <= n; x += ((x) & (-(x)))) c[x] += y;
}
inline long long query(int x) {
  long long res = 0;
  for (; x; x -= ((x) & (-(x)))) res += c[x];
  return res;
}
int main() {
  n = rd();
  for (int i = 1; i <= n; i++) S[i] = rd(), M[i] = rd(), R[i] = rd();
  for (int i = 1; i <= n; i++) st.insert(node(i, i, 0));
  m = rd();
  for (int i = 1; i <= m; i++) {
    int t = rd(), l = rd(), r = rd();
    if (r < n) split(r + 1);
    for (set<node>::iterator it = split(l); it != st.end() && it->l <= r;
         st.erase(it++)) {
      if (it->t == 0)
        pre_gao(it->l, it->r, t, i);
      else
        h[++tt] = (hhhh){it->l, it->r, t - it->t, i};
    }
    st.insert(node(l, r, t));
  }
  sort(h + 1, h + tt + 1, cmp);
  for (int i = 1; i <= n; i++) g[i] = i;
  sort(g + 1, g + n + 1, cmp1);
  build(1, 1, n);
  int now = 1;
  for (int i = 1; i <= tt; i++) {
    for (; now <= n && R[g[now]] && M[g[now]] / R[g[now]] + 1 <= h[i].t;
         now++) {
      del(1, 1, n, g[now]);
      add(g[now], M[g[now]]);
    }
    gao(1, h[i].t - h[i - 1].t);
    ans[h[i].id] +=
        query(1, 1, n, h[i].l, h[i].r) + query(h[i].r) - query(h[i].l - 1);
  }
  for (int i = 1; i <= m; i++) print(ans[i]);
  return 0;
}