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;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
const int inf = 1e9 + 143;
const long long longinf = 1e18 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = 105000;
const int BLOCK = 200;
const int NBLOCK = N / BLOCK + 5;
int s[N], m[N], r[N];
struct info {
  int s, m, r, id;
  int end_time() const {
    if (r == 0) return inf;
    return (m + r - 1) / r;
  }
  friend bool operator<(const info &a, const info &b) {
    return a.end_time() < b.end_time();
  }
};
inline long long range_sum(long long *s, int l, int r) {
  if (!s || l > r) return 0ll;
  return s[r] - (l ? s[l - 1] : 0ll);
}
class block {
  info a[BLOCK + 5];
  info zero[BLOCK + 5];
  long long sumr[BLOCK + 5], summ[BLOCK + 5];
  int etime[BLOCK + 5];
  int t_reset;
  bool is_zero;
  int from, to;
  int sz;

 public:
  block() {}
  block(int _from, int _to) {
    from = _from;
    to = _to;
    is_zero = false;
    t_reset = 0;
    sz = 0;
    for (int i = from; i <= to; i++) {
      a[sz] = {s[i], m[i], r[i], i};
      zero[sz] = {0, m[i], r[i], i};
      sz++;
    }
    sort(zero, zero + sz);
    for (int i = 0; i < sz; i++) {
      etime[i] = zero[i].end_time();
      sumr[i] = zero[i].r;
      summ[i] = zero[i].m;
      if (i > 0) {
        sumr[i] += sumr[i - 1];
        summ[i] += summ[i - 1];
      }
    }
  }
  long long query(int l, int r, int t) {
    if (l > to || r < from) return 0;
    if (l <= from && r >= to && is_zero) {
      int x = t - t_reset;
      int lo = upper_bound(etime, etime + sz, x) - etime;
      return range_sum(sumr, lo, sz - 1) * x + range_sum(summ, 0, lo - 1);
    } else {
      long long res = 0;
      for (int i = 0; i < sz; i++)
        if (a[i].id >= l && a[i].id <= r)
          res += min((is_zero ? 0 : a[i].s) + (long long)a[i].r * (t - t_reset),
                     (long long)a[i].m);
      return res;
    }
  }
  void take(int l, int r, int t) {
    if (l > to || r < from) return;
    if (l <= from && r >= to) {
      is_zero = true;
      t_reset = t;
    } else {
      for (int i = 0; i < sz; i++) {
        if (a[i].id >= l && a[i].id <= r) {
          a[i].s = 0;
        } else {
          a[i].s =
              min((long long)a[i].m,
                  (is_zero ? 0 : a[i].s) + (long long)a[i].r * (t - t_reset));
        }
      }
      t_reset = t;
      is_zero = false;
    }
  }
};
int n;
block b[NBLOCK];
int main() {
  n = read();
  for (int i = 0; i < n; i++) {
    s[i] = read();
    m[i] = read();
    r[i] = read();
  }
  for (int i = 0; i * BLOCK < n; i++) {
    b[i] = block(i * BLOCK, min(n - 1, i * BLOCK + BLOCK - 1));
  }
  int q = read();
  for (int qq = 0; qq < q; qq++) {
    int t = read();
    int l = read() - 1;
    int r = read() - 1;
    long long res = 0;
    for (int i = 0; i * BLOCK < n; i++) {
      res += b[i].query(l, r, t);
      b[i].take(l, r, t);
    }
    printf("%I64d\n", res);
  }
  return 0;
}