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;
int N;
int s[100005], m[100005], f[100005];
int M;
int t[100005], l[100005], r[100005];
struct interval {
  int l, r, t;
  interval() {}
  interval(int l, int r, int t) : l(l), r(r), t(t) {}
  friend bool operator<(const interval &a, const interval &b) {
    return a.r < b.r;
  }
};
set<interval> I;
struct event {
  int delta, x, y;
  int qid, type;
  event() {}
  event(int delta, int x, int y, int qid, int type)
      : delta(delta), x(x), y(y), qid(qid), type(type) {}
  friend bool operator<(const event &a, const event &b) {
    if (a.delta == b.delta) return a.type < b.type;
    return a.delta < b.delta;
  }
};
vector<event> E;
long long rate[100005];
long long top[100005];
void update(long long *f, int x, int v) {
  for (int i = x + 1; i < 100005; i += i & -i) f[i] += v;
}
long long query(long long *f, int x, int y) {
  long long ret = 0;
  for (int i = y + 1; i; i -= i & -i) ret += f[i];
  for (int i = x; i; i -= i & -i) ret -= f[i];
  return ret;
}
long long sol[100005];
void build_events() {
  for (int i = (0); i < (N); ++i) I.insert(interval(i, i, -1));
  for (int i = (0); i < (M); ++i) {
    --l[i], --r[i];
    for (auto it = I.lower_bound({l[i], l[i], 0});
         it != I.end() && it->l <= r[i]; it = I.lower_bound({l[i], l[i], 0})) {
      interval ci = *it;
      I.erase(it);
      if (ci.l < l[i]) {
        I.insert(interval(ci.l, l[i] - 1, ci.t));
        I.insert(interval(l[i], ci.r, ci.t));
      } else if (ci.r > r[i]) {
        I.insert(interval(r[i] + 1, ci.r, ci.t));
        I.insert(interval(ci.l, r[i], ci.t));
      } else if (ci.t == -1) {
        sol[i] += min((long long)m[ci.l], (long long)f[ci.l] * t[i] + s[ci.l]);
      } else {
        E.push_back(event(t[i] - ci.t, ci.l, ci.r, i, 1));
      }
    }
    I.insert(interval(l[i], r[i], t[i]));
  }
  for (int i = (0); i < (N); ++i)
    E.push_back(event(f[i] ? (m[i] + f[i] - 1) / f[i] : 0, i, 0, 0, 0));
}
void sweep() {
  sort(E.begin(), E.end());
  for (int i = (0); i < (N); ++i) {
    update(rate, i, f[i]);
    if (f[i] == 0) m[i] = 0;
  }
  for (auto &e : E) {
    if (e.type == 0) {
      update(rate, e.x, -f[e.x]);
      update(top, e.x, +m[e.x]);
    } else {
      sol[e.qid] += e.delta * query(rate, e.x, e.y) + query(top, e.x, e.y);
    }
  }
}
int main(void) {
  scanf("%d", &N);
  for (int i = (0); i < (N); ++i) scanf("%d%d%d", &s[i], &m[i], &f[i]);
  scanf("%d", &M);
  for (int i = (0); i < (M); ++i) scanf("%d%d%d", &t[i], &l[i], &r[i]);
  build_events();
  sweep();
  for (int i = (0); i < (M); ++i) cout << sol[i] << endl;
  return 0;
}