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 void read(int &x) {
  int flg = 1;
  char ch;
  while (!isdigit(ch = getchar()))
    if (ch == '-') flg = -flg;
  for (x = ch - '0'; isdigit(ch = getchar()); x = x * 10 + ch - '0')
    ;
  x *= flg;
}
const int MAXN = 100005;
const int MAXM = MAXN * 30;
const int inf = 2000000000;
int n, Q, mx, s[MAXN], m[MAXN], r[MAXN], t[MAXN];
int tot, lc[MAXM], rc[MAXM], rt[MAXN];
long long sr[MAXM], sm[MAXM];
void ins(int &i, int L, int R, int x, int vr, int vm) {
  ++tot;
  lc[tot] = lc[i], rc[tot] = rc[i];
  sr[tot] = sr[i] + vr;
  sm[tot] = sm[i] + vm;
  i = tot;
  if (L == R) return;
  int mid = (L + R) >> 1;
  x <= mid ? ins(lc[i], L, mid, x, vr, vm) : ins(rc[i], mid + 1, R, x, vr, vm);
}
long long qry(int i, int L, int R, int x, int y, int v) {
  if (!i) return 0;
  if (x <= L && R <= y) return v ? sm[i] : sr[i];
  int mid = (L + R) >> 1;
  long long re = 0;
  if (x <= mid) re += qry(lc[i], L, mid, x, y, v);
  if (y > mid) re += qry(rc[i], mid + 1, R, x, y, v);
  return re;
}
struct node {
  pair<int, int> x;
  int y;
  node(int a = 0, int b = 0, int c = 0) {
    x = pair<int, int>(a, b);
    y = c;
  }
  inline bool operator<(const node &o) const {
    return x == o.x ? y < o.y : x < o.x;
  }
};
set<node> st;
set<node>::iterator split_l(int x) {
  set<node>::iterator it = st.upper_bound(node(x, n + 1, 0));
  --it;
  if (it->x.first < x) {
    int L = it->x.first, R = it->x.second, t = it->y;
    st.erase(it);
    st.insert(node(L, x - 1, t));
    return st.insert(node(x, R, t)).first;
  } else
    return it;
}
set<node>::iterator split_r(int x) {
  set<node>::iterator it = st.upper_bound(node(x, n + 1, 0));
  --it;
  if (it->x.second > x) {
    int L = it->x.first, R = it->x.second, t = it->y;
    st.erase(it);
    st.insert(node(x + 1, R, t));
    return st.insert(node(L, x, t)).first;
  } else
    return it;
}
long long cal(int L, int R, int t) {
  long long re = 0;
  if (L == R) {
    int tmp = r[L] ? (m[L] - s[L] + r[L] - 1) / r[L] : inf;
    if (t >= tmp)
      re = m[L];
    else
      re = s[L] + r[L] * t;
    s[L] = 0;
    return re;
  }
  t = min(t, mx - 1);
  re += t *
        (qry(rt[R], 1, mx, t + 1, mx, 0) - qry(rt[L - 1], 1, mx, t + 1, mx, 0));
  if (t >= 1) re += qry(rt[R], 1, mx, 1, t, 1) - qry(rt[L - 1], 1, mx, 1, t, 1);
  return re;
}
int main() {
  read(n);
  mx = 1;
  for (int i = 1; i <= n; ++i) {
    read(s[i]), read(m[i]), read(r[i]);
    if (r[i])
      mx = max(mx, t[i] = (m[i] + r[i] - 1) / r[i]);
    else
      t[i] = -1;
    st.insert(node(i, i, 0));
  }
  ++mx;
  for (int i = 1; i <= n; ++i)
    ins(rt[i] = rt[i - 1], 1, mx, (~t[i]) ? t[i] : mx, r[i], m[i]);
  read(Q);
  int t, L, R;
  while (Q--) {
    read(t), read(L), read(R);
    set<node>::iterator itL = split_l(L), itR = split_r(R);
    long long ans = 0;
    if (itR->x.first == L && itR->x.second == R)
      ans += cal(L, R, t - itR->y), st.erase(itR);
    else {
      for (set<node>::iterator i = itL; i != itR;)
        ans += cal(i->x.first, i->x.second, t - i->y), st.erase(i++);
      ans += cal(itR->x.first, itR->x.second, t - itR->y), st.erase(itR);
    }
    st.insert(node(L, R, t));
    t -= 2;
    printf("%lld\n", ans);
  }
}