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;
const int N = 1e5 + 4;
int n, m;
struct node {
  long long s, a, b, rate;
  node() { s = a = b = rate = 0; }
  bool friend operator<(const node &a, const node &b) {
    return a.rate < b.rate;
  }
} p[20][N], x[N];
long long ans;
long long sa[20][N], sb[20][N], day[N << 2];
void build(int l, int r, int o, int d) {
  day[o] = -2;
  if (l == r) {
    p[d][l] = x[l];
    sa[d][l] = x[l].a + sa[d][l - 1];
    sb[d][l] = x[l].b + sb[d][l - 1];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, o << 1, d + 1);
  build(mid + 1, r, o << 1 | 1, d + 1);
  int i = l, j = mid + 1, cnt = l - 1;
  while (i <= mid && j <= r) {
    if (p[d + 1][i] < p[d + 1][j])
      p[d][++cnt] = p[d + 1][i++];
    else
      p[d][++cnt] = p[d + 1][j++];
  }
  while (i <= mid) p[d][++cnt] = p[d + 1][i++];
  while (j <= r) p[d][++cnt] = p[d + 1][j++];
  for (int i = l; i <= r; ++i) {
    sa[d][i] = sa[d][i - 1] + p[d][i].a;
    sb[d][i] = sb[d][i - 1] + p[d][i].b;
  }
}
void pushdown(int x) {
  if (day[x] < 0) return;
  day[x << 1] = day[x << 1 | 1] = day[x];
}
void query(int l, int r, int o, int a, int b, long long t, int d) {
  if (l > b || r < a) return;
  if (l >= a && r <= b && day[o] != -1) {
    if (day[o] == -2)
      for (int i = l; i <= r; ++i) ans += min(x[i].b, x[i].s + x[i].a * t);
    else {
      node w;
      w.rate = t - day[o];
      int i = upper_bound(p[d] + l, p[d] + r + 1, w) - p[d] - 1;
      ans += (t - day[o]) * (sa[d][r] - sa[d][i]) + sb[d][i] - sb[d][l - 1];
    }
    day[o] = t;
    return;
  }
  pushdown(o);
  int mid = (l + r) >> 1;
  query(l, mid, o << 1, a, b, t, d + 1);
  query(mid + 1, r, o << 1 | 1, a, b, t, d + 1);
  day[o] = day[o << 1] == day[o << 1 | 1] ? day[o << 1] : -1;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d %I64d %I64d", &x[i].s, &x[i].b, &x[i].a);
    if (x[i].a == 0)
      x[i].rate = 1LL << 60;
    else
      x[i].rate = (x[i].b + x[i].a - 1) / x[i].a;
  }
  scanf("%d", &m);
  build(1, n, 1, 0);
  while (m--) {
    long long t, l, r;
    scanf("%I64d %I64d %I64d", &t, &l, &r);
    ans = 0;
    query(1, n, 1, l, r, t, 0);
    printf("%I64d\n", ans);
  }
  return 0;
}