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;
vector<pair<int, pair<long long, long long> > > hop[4 * 100100];
int s[100100], t[4 * 100100];
void insert(int u, int L, int R, int pos,
            pair<int, pair<long long, long long> > d) {
  if (L > pos || R <= pos) return;
  hop[u].push_back(d);
  if (R == L + 1) return;
  int ls = 2 * u, rs = 2 * u + 1;
  int mid = (L + R) >> 1;
  insert(ls, L, mid, pos, d);
  insert(rs, mid, R, pos, d);
  return;
}
void Hope(int u, int L, int R) {
  hop[u].push_back(pair<int, pair<long long, long long> >(
      0, pair<long long, long long>(0, 0)));
  vector<pair<int, pair<long long, long long> > > &v = hop[u];
  sort(v.begin(), v.end());
  for (int i = 0, deg = v.size(); i + 1 < deg; i++) {
    v[i + 1].second.first += v[i].second.first;
    v[i + 1].second.second += v[i].second.second;
  }
  if (R == L + 1) return;
  int mid = (L + R) >> 1;
  int ls = 2 * u, rs = 2 * u + 1;
  Hope(ls, L, mid);
  Hope(rs, mid, R);
  return;
}
void Push_down(int u) {
  int ls = 2 * u, rs = 2 * u + 1;
  t[ls] = max(t[ls], t[u]);
  t[rs] = max(t[rs], t[u]);
  return;
}
long long calc(int u, int L, int R, int l, int r, int T) {
  if (L >= r || l >= R) return 0;
  if (l <= L && R <= r && t[u]) {
    T -= t[u];
    int p = lower_bound(hop[u].begin(), hop[u].end(),
                        pair<int, pair<long long, long long> >(
                            T, pair<long long, long long>(-1, -1))) -
            hop[u].begin() - 1;
    long long val = (hop[u].back().second.first - hop[u][p].second.first) * T +
                    hop[u][p].second.second;
    t[u] += T;
    return val;
  }
  if (R == L + 1) {
    long long val =
        min(s[L] + T * hop[u][1].second.first, hop[u][1].second.second);
    t[u] = T;
    return val;
  }
  int ls = 2 * u, rs = 2 * u + 1;
  int mid = (L + R) >> 1;
  Push_down(u);
  long long val = calc(ls, L, mid, l, r, T) + calc(rs, mid, R, l, r, T);
  if (t[ls] == t[rs])
    t[u] = t[ls];
  else
    t[u] = 0;
  return val;
}
int main() {
  int N, m, r, M, T, l;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d%d%d", s + i, &m, &r);
    insert(1, 0, N, i,
           pair<int, pair<long long, long long> >(
               r ? m / r : 1000000100, pair<long long, long long>(r, m)));
  }
  Hope(1, 0, N);
  for (scanf("%d", &M); M--;) {
    scanf("%d%d%d", &T, &l, &r);
    l--;
    printf("%I64d\n", calc(1, 0, N, l, r, T));
  }
  return 0;
}