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, q, a[100010], m[100010], r[100010];
struct par {
  int l, r, t, v;
  bool operator<(const par &B) const { return l < B.l; }
};
set<par> s;
long long sm[100010 * 20], sr[100010 * 20];
int ls[100010 * 20], rs[100010 * 20], id = 0, rt[100010];
void add_node(int from, int &to, int l, int r, int x, int pos) {
  to = ++id;
  sm[to] = sm[from] + ::m[pos];
  sr[to] = sr[from] + ::r[pos];
  if (l == r) return;
  int mid = l + r >> 1;
  if (x <= mid)
    add_node(ls[from], ls[to], l, mid, x, pos), rs[to] = rs[from];
  else
    add_node(rs[from], rs[to], mid + 1, r, x, pos), ls[to] = ls[from];
}
long long askr(int now, int l, int r, int x) {
  if (!now) return 0;
  if (x == l) return sr[now];
  int mid = l + r >> 1;
  if (x <= mid)
    return askr(ls[now], l, mid, x) + sr[rs[now]];
  else
    return askr(rs[now], mid + 1, r, x);
}
long long askm(int now, int l, int r, int x) {
  if (!now) return 0;
  if (x == r) return sm[now];
  int mid = l + r >> 1;
  if (x >= mid + 1)
    return askm(rs[now], mid + 1, r, x) + sm[ls[now]];
  else
    return askm(ls[now], l, mid, x);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d %d", &a[i], &m[i], &r[i]);
    s.insert((par){i, i, 0, 1});
    if (r[i] && m[i])
      add_node(rt[i - 1], rt[i], 0, 100010 - 10, m[i] / r[i], i);
    else
      rt[i] = rt[i - 1];
  }
  scanf("%d", &q);
  for (int i = 1, t, l, r; i <= q; i++) {
    scanf("%d %d %d", &t, &l, &r);
    par p = *(--s.upper_bound((par){l, 0, 0, 0}));
    if (p.l != l) {
      s.erase(p);
      s.insert((par){p.l, l - 1, p.t, p.v});
      s.insert((par){l, p.r, p.t, p.v});
    }
    p = *(--s.upper_bound((par){r, 0, 0, 0}));
    if (p.r != r) {
      s.erase(p);
      s.insert((par){p.l, r, p.t, p.v});
      s.insert((par){r + 1, p.r, p.t, p.v});
    }
    long long ans = 0;
    while (s.lower_bound((par){l, 0, 0, 0}) != s.end() &&
           (p = *s.lower_bound((par){l, 0, 0, 0})).l <= r) {
      if (p.v) {
        ans += min(a[p.l] + 1ll * (t - p.t) * ::r[p.l], (long long)::m[p.l]);
      } else {
        if (t - p.t >= 100010 - 10) {
          ans += sm[rt[p.r]] - sm[rt[p.l - 1]];
        } else {
          long long R = askr(rt[p.r], 0, 100010 - 10, t - p.t) -
                        askr(rt[p.l - 1], 0, 100010 - 10, t - p.t);
          long long M = askm(rt[p.r], 0, 100010 - 10, t - p.t - 1) -
                        askm(rt[p.l - 1], 0, 100010 - 10, t - p.t - 1);
          ans += R * (t - p.t) + M;
        }
      }
      s.erase(p);
    }
    s.insert((par){l, r, t, 0});
    printf("%lld\n", ans);
  }
}