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;
long long b[100007], bg[327], ed[327], need[327];
int n;
long long am[327][100007], tme[100007];
long long s[100007], m[100007], r[100007];
void build() {
  for (int i = 0; i < 327; i++) bg[i] = ed[i] = 1e18 + 7;
  bg[0] = 0;
  for (int i = 1; i < n; i++) {
    b[i] = i / 327;
    if (b[i] != b[i - 1]) {
      bg[b[i]] = i;
      ed[b[i - 1]] = i - 1;
    }
  }
  ed[b[n - 1]] = n - 1;
}
void update(int bq) {
  if (need[bq] == -1) return;
  for (int i = bg[bq]; i <= ed[bq]; i++) tme[i] = need[bq];
  need[bq] = -1;
}
long long calc(long long t, int i) {
  long long ans = min(s[i] + (t - tme[i]) * r[i], m[i]);
  s[i] = 0;
  tme[i] = t;
  return ans;
}
long long query(int t, int l, int r) {
  update(b[l]);
  update(b[r]);
  long long ans = 0;
  if (b[l] == b[r]) {
    for (int i = l; i <= r; i++) ans += calc(t, i);
    return ans;
  }
  int bl = b[l] + 1, br = b[r] - 1;
  for (int i = l; i <= ed[b[l]]; i++) ans += calc(t, i);
  need[b[l]] = -1;
  for (int i = bl; i <= br; i++) {
    if (need[i] != -1)
      ans += am[i][min((t - need[i]), 100007 - 1LL)];
    else {
      for (int j = bg[i]; j <= ed[i]; j++) ans += calc(t, j);
    }
    need[i] = t;
  }
  for (int i = bg[b[r]]; i <= r; i++) ans += calc(t, i);
  need[b[r]] = -1;
  return ans;
}
int main() {
  scanf("%d", &n);
  build();
  for (int i = 0; i < n; i++) {
    scanf("%lld %lld %lld", &s[i], &m[i], &r[i]);
    if (r[i] == 0) continue;
    int t = m[i] / r[i];
    am[b[i]][1] += r[i];
    am[b[i]][t + 1] += (m[i] % r[i]) - r[i];
    am[b[i]][t + 2] -= (m[i] % r[i]);
  }
  for (int i = 0; ed[i] != 1e18 + 7; i++) {
    need[i] = -1;
    for (int j = 2; j < 100007; j++) am[i][j] += am[i][j - 1];
    for (int j = 2; j < 100007; j++) am[i][j] += am[i][j - 1];
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    l--;
    r--;
    printf("%lld\n", query(t, l, r));
  }
  return 0;
}