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>
const int MAXN = 1e5 + 5;
int n, q;
int s[MAXN], m[MAXN], d[MAXN];
std::vector<std::pair<int, int> > add[MAXN], del[MAXN];
long long ans[MAXN];
long long sd[MAXN << 5], sm[MAXN << 5];
int lc[MAXN << 5], rc[MAXN << 5], tot;
inline void insert(int prev, int &v, int l, int r, int p, int m, int d) {
  sd[v = ++tot] = sd[prev] + d;
  sm[v] = sm[prev] + m;
  lc[v] = lc[prev];
  rc[v] = rc[prev];
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (p <= mid)
    insert(lc[prev], lc[v], l, mid, p, m, d);
  else
    insert(rc[prev], rc[v], mid + 1, r, p, m, d);
}
inline long long query(int x, int y, int l, int r, int L, int R, int o) {
  if (L > R) return 0;
  if (l == L && r == R) return o == 0 ? sd[y] - sd[x] : sm[y] - sm[x];
  int mid = (l + r) >> 1;
  if (R <= mid) return query(lc[x], lc[y], l, mid, L, R, o);
  if (L > mid) return query(rc[x], rc[y], mid + 1, r, L, R, o);
  return query(lc[x], lc[y], l, mid, L, mid, o) +
         query(rc[x], rc[y], mid + 1, r, mid + 1, R, o);
}
int rt[MAXN];
struct Node {
  int x, st, id;
  Node(int x = 0, int st = 0, int id = 0) : x(x), st(st), id(id) {}
  bool operator<(const Node &t) const { return x < t.x; }
};
std::set<Node> st;
std::vector<int> S;
inline void upd(std::set<Node>::iterator p, int now) {
  if (p == st.begin()) return;
  if (p->st == now) return;
  int len = p->x - prev(p)->x, L = p->st, R = now - 1;
  int ps = std::lower_bound(S.begin(), S.end(), len) - S.begin();
  ans[p->id] += query(rt[L - 1], rt[R], 1, ((int)S.size()), 1, ps, 1);
  ans[p->id] +=
      query(rt[L - 1], rt[R], 1, ((int)S.size()), ps + 1, ((int)S.size()), 0) *
      len;
  Node tmp = *p;
  tmp.st = now;
  st.erase(p);
  st.insert(tmp);
}
inline void insert(int x, int now, int id) {
  auto p = st.lower_bound(Node(x));
  if (p != st.end()) upd(p, now);
  st.insert(Node(x, now, id));
}
inline void erase(int x, int now, int id) {
  auto p = st.upper_bound(Node(x));
  if (p != st.end()) upd(p, now);
  p = st.lower_bound(Node(x));
  upd(p, now);
  st.erase(st.lower_bound(Node(x)));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", s + i, m + i, d + i);
    if (d[i]) S.emplace_back(m[i] / d[i]);
  }
  std::sort(S.begin(), S.end());
  S.erase(std::unique(S.begin(), S.end()), S.end());
  for (int i = 1; i <= n; ++i) {
    if (d[i])
      insert(rt[i - 1], rt[i], 1, ((int)S.size()),
             std::lower_bound(S.begin(), S.end(), m[i] / d[i]) - S.begin() + 1,
             m[i], d[i]);
    else
      rt[i] = rt[i - 1];
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    add[l].emplace_back(t, i);
    del[r + 1].emplace_back(t, i);
  }
  for (int i = 1; i <= n + 1; ++i) {
    for (auto x : add[i]) {
      insert(x.first, i, x.second);
    }
    for (auto x : del[i]) {
      erase(x.first, i, x.second);
    }
    if (i <= n && !st.empty()) {
      Node p = *st.begin();
      ans[p.id] += std::min(1ll * m[i], 1ll * p.x * d[i] + s[i]);
      st.erase(p);
      p.st = i + 1;
      st.insert(p);
    }
  }
  for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
  return 0;
}