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>
clock_t __t = clock();
namespace my_std {
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
inline T rnd(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T &t) {
  t = 0;
  char f = 0, ch = getchar();
  double d = 0.1;
  while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
  while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
  if (ch == '.') {
    ch = getchar();
    while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
  }
  t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
char __sr[1 << 21], __z[20];
int __C = -1, __zz = 0;
inline void Ot() { fwrite(__sr, 1, __C + 1, stdout), __C = -1; }
inline void print(register int x) {
  if (__C > 1 << 20) Ot();
  if (x < 0) __sr[++__C] = '-', x = -x;
  while (__z[++__zz] = x % 10 + 48, x /= 10)
    ;
  while (__sr[++__C] = __z[__zz], --__zz)
    ;
  __sr[++__C] = '\n';
}
void file() {}
inline void chktime() {}
long long ksm(long long x, int y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
}  // namespace my_std
using namespace my_std;
int n;
int sss[101001], M[101001], R[101001];
int vis[101001];
struct hh {
  long long m, r;
  hh(long long M = 0, long long R = 0) { m = M, r = R; }
  const hh operator+(const hh &x) const { return hh(m + x.m, r + x.r); }
};
namespace SegmentTree {
hh sum[101001 * 20];
int ls[101001 * 20], rs[101001 * 20], cnt;
int root[101001];
void insert(int &k, int l, int r, int x, hh w, int pre) {
  k = ++cnt;
  ls[k] = ls[pre], rs[k] = rs[pre], sum[k] = sum[pre] + w;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    insert(ls[k], l, mid, x, w, ls[pre]);
  else
    insert(rs[k], mid + 1, r, x, w, rs[pre]);
}
hh query(int k, int l, int r, int x, int y) {
  if (!k) return hh();
  if (x <= l && r <= y) return sum[k];
  int mid = (l + r) >> 1;
  hh ret;
  if (x <= mid) ret = ret + query(ls[k], l, mid, x, y);
  if (y > mid) ret = ret + query(rs[k], mid + 1, r, x, y);
  return ret;
}
}  // namespace SegmentTree
using namespace SegmentTree;
struct hhh {
  int l, r, t;
  hhh(int L = 0, int R = 0, int T = 0) { l = L, r = R, t = T; }
  const bool operator<(const hhh &x) const { return l < x.l; }
};
set<hhh> s;
set<hhh>::iterator split(int pos) {
  auto it = s.upper_bound(hhh(pos, 0, 0));
  --it;
  if ((*it).r < pos) return s.end();
  hhh x = *it, y = *it;
  s.erase(it);
  x.r = pos - 1, y.l = pos;
  if (x.l <= x.r) s.insert(x);
  return s.insert(y).first;
}
int main() {
  file();
  read(n);
  for (int i = (1); i <= (n); i++) read(sss[i], M[i], R[i]);
  for (int i = (1); i <= (n); i++)
    if (R[i])
      insert(root[i], 1, 100000, (M[i] - 1) / R[i] + 1, hh(M[i], R[i]),
             root[i - 1]);
    else
      root[i] = root[i - 1];
  for (int i = (1); i <= (n); i++) s.insert(hhh(i, i, 0));
  int Q;
  read(Q);
  for (int _ = (1); _ <= (Q); _++) {
    long long tt;
    int l, r;
    read(tt, l, r);
    auto it2 = split(r + 1), it1 = split(l);
    long long ans = 0;
    for (auto it = it1; it != it2; s.erase(it++)) {
      int l = (*it).l, r = (*it).r, T = (*it).t;
      if (l == r && !vis[l])
        ans += min((long long)M[l], tt * R[l] + sss[l]), vis[l] = 1;
      else {
        T = tt - T;
        ans += query(root[r], 1, 100000, 1, T).m -
               query(root[l - 1], 1, 100000, 1, T).m;
        ans += (query(root[r], 1, 100000, T + 1, 100000).r -
                query(root[l - 1], 1, 100000, T + 1, 100000).r) *
               T;
      }
    }
    printf("%I64d\n", ans);
    s.insert(hhh(l, r, tt));
  }
  return 0;
}