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 = 100010;
struct Point {
  int t, l, r, dep;
} Q[N];
int n, M, s[N], m[N], v[N];
long long ans[N];
struct Node {
  int l, r, dep, lazy, now, t;
  long long tmp;
  vector<int> v;
} t[N * 4];
long long f[20][N], h[20][N];
int g[20][N];
long long cal(int x, int y) {
  int l = t[x].l, r = t[x].r + 1, mid, dep = t[x].dep;
  while (l < r) {
    mid = (l + r) / 2;
    if (m[g[dep][mid]] > 1LL * y * v[g[dep][mid]])
      r = mid;
    else
      l = mid + 1;
  }
  return f[dep][l - 1] - f[dep][t[x].l - 1] +
         1LL * y * (h[dep][t[x].r] - h[dep][l - 1]);
}
void build(int x, int l, int r) {
  t[x].l = l, t[x].r = r;
  t[x].now = 0;
  t[x].lazy = -1;
  t[x].t = 0;
  t[x].tmp = 0;
  t[x].dep = t[x / 2].dep + 1;
  if (l == r) {
    g[t[x].dep][l] = l;
    return;
  }
  int mid = (l + r) / 2;
  build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);
  int dep = t[x].dep, L = l, R = mid + 1, now = l;
  while (now <= r) {
    if (L <= mid && (R > r || 1LL * m[g[dep + 1][L]] * v[g[dep + 1][R]] <=
                                  1LL * m[g[dep + 1][R]] * v[g[dep + 1][L]])) {
      g[dep][now++] = g[dep + 1][L++];
    } else
      g[dep][now++] = g[dep + 1][R++];
  }
}
void insert(int x, int y, int l, int r) {
  if (l == t[x].l && r == t[x].r) {
    t[x].v.push_back(y);
    return;
  }
  int mid = (t[x].l + t[x].r) / 2;
  if (r <= mid)
    insert(x * 2, y, l, r);
  else if (l > mid)
    insert(x * 2 + 1, y, l, r);
  else {
    insert(x * 2, y, l, mid);
    insert(x * 2 + 1, y, mid + 1, r);
  }
}
void push(int x) {
  if (t[x].lazy == -1) return;
  t[x].t = t[x].lazy;
  t[x].tmp = 0;
  if (t[x].l < t[x].r) t[x * 2].lazy = t[x * 2 + 1].lazy = t[x].lazy;
  t[x].lazy = -1;
}
void Query(int x, int y, int l, int r) {
  push(x);
  if (l == t[x].l && r == t[x].r) {
    ans[y] += t[x].tmp;
    t[x].tmp = 0;
    ans[y] += cal(x, Q[y].t - t[x].t);
    t[x].now++;
    int z = x / 2, tmp = 0, tmp1;
    while (z) {
      if (t[z].v.size() > t[z].now) {
        if (tmp == 0 || Q[t[z].v[t[z].now]].t < Q[tmp].t)
          tmp = t[z].v[t[z].now], tmp1 = z;
      }
      z /= 2;
    }
    z = tmp1;
    if (tmp != 0) {
      t[z].tmp -= cal(x, Q[tmp].t - t[x].t);
      t[z].tmp += cal(x, Q[tmp].t - Q[y].t);
    }
    t[x].lazy = Q[y].t;
    return;
  }
  int mid = (t[x].l + t[x].r) / 2;
  if (r <= mid)
    Query(x * 2, y, l, r);
  else if (l > mid)
    Query(x * 2 + 1, y, l, r);
  else {
    Query(x * 2, y, l, mid);
    Query(x * 2 + 1, y, mid + 1, r);
  }
}
void retrieve(int x, int l, int r) {
  if (l == r) {
    int y = x, tmp = 0, tmp1;
    while (y) {
      if (t[y].v.size() > 0) {
        if (tmp == 0 || Q[t[y].v[0]].t < Q[tmp].t) tmp = t[y].v[0], tmp1 = y;
      }
      y /= 2;
    }
    y = tmp1;
    if (tmp == 0) return;
    if (cal(x, Q[tmp].t) <= m[l] - s[l])
      t[y].tmp += s[l];
    else
      t[y].tmp += m[l] - cal(x, Q[tmp].t);
    return;
  }
  int mid = (l + r) / 2;
  retrieve(x * 2, l, mid);
  retrieve(x * 2 + 1, mid + 1, r);
}
int main() {
  t[0].dep = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", s + i, m + i, v + i);
    if (v[i] == 0) m[i]++;
  }
  scanf("%d", &M);
  for (int i = 1; i <= M; i++) scanf("%d%d%d", &Q[i].t, &Q[i].l, &Q[i].r);
  build(1, 1, n);
  for (int i = 1; i <= 19; i++) {
    for (int j = 1; j <= n; j++) f[i][j] = m[g[i][j]], h[i][j] = v[g[i][j]];
    for (int j = 1; j <= n; j++) f[i][j] += f[i][j - 1], h[i][j] += h[i][j - 1];
  }
  for (int i = 1; i <= M; i++) insert(1, i, Q[i].l, Q[i].r);
  retrieve(1, 1, n);
  for (int i = 1; i <= M; i++) {
    Query(1, i, Q[i].l, Q[i].r);
  }
  for (int i = 1; i <= M; i++) printf("%I64d\n", ans[i]);
  return 0;
}