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 inf = 2147483647;
const int N = 100001;
int _max(int x, int y) { return x > y ? x : y; }
int _min(int x, int y) { return x < y ? x : y; }
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * f;
}
void put(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) put(x / 10);
  putchar(x % 10 + '0');
}
int s[N], m[N], R[N];
long long s2[N];
int get1(int x) { return R[x] == 0 ? 999999999 : (m[x] - s[x] - 1) / R[x] + 1; }
int get2(int x) { return R[x] == 0 ? 999999999 : (m[x] - 1) / R[x] + 1; }
bool cmp1(int a, int b) { return get1(a) < get1(b); }
bool cmp2(int a, int b) { return get2(a) < get2(b); }
struct seg {
  int cnt, lc[N << 1], rc[N << 1], c[N << 1], tt[N << 1], o[N << 1];
  vector<long long> s1[N << 1], s3[N << 1];
  vector<int> q[N << 1];
  void bt(int l, int r) {
    int now = ++cnt;
    for (int i = l; i <= r; i++) q[now].push_back(i);
    sort(q[now].begin(), q[now].end(), cmp1);
    long long S = 0;
    for (int i = 0; i <= r - l; i++) S += R[q[now][i]], s1[now].push_back(S);
    S = 0;
    for (int i = 0; i <= r - l; i++)
      S += s[q[now][i]] - m[q[now][i]], s3[now].push_back(S);
    if (l < r) {
      int mid = (l + r) / 2;
      lc[now] = cnt + 1, bt(l, mid);
      rc[now] = cnt + 1, bt(mid + 1, r);
    }
  }
  void change(int now, int l, int r) {
    o[now] = 1;
    sort(q[now].begin(), q[now].end(), cmp2);
    int len = r - l + 1;
    s1[now].clear(), s3[now].clear();
    long long S = 0;
    for (int i = 0; i < len; i++) S += R[q[now][i]], s1[now].push_back(S);
    S = 0;
    for (int i = 0; i < len; i++) S += m[q[now][i]], s3[now].push_back(S);
  }
  long long solve(int now, int L, int R, int T) {
    if (tt[now] && !o[now]) change(now, L, R);
    int l = 0, r = R - L, hh = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (T - tt[now] >= (tt[now] == 0 ? get1(q[now][mid]) : get2(q[now][mid])))
        hh = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    long long ans = 0;
    if (tt[now] == 0)
      ans += s2[R] - s2[L - 1] +
             (s1[now][R - L] - (hh == -1 ? 0 : s1[now][hh])) * (T - tt[now]) +
             s3[now][R - L] - (hh == -1 ? 0 : s3[now][hh]);
    else
      ans += (hh == -1 ? 0 : s3[now][hh]) +
             (s1[now][R - L] - (hh == -1 ? 0 : s1[now][hh])) * (T - tt[now]);
    return ans;
  }
  void pushdown(int now, int l, int r) {
    if (c[now] == 0) {
      c[lc[now]] = c[rc[now]] = 0;
      int mid = (l + r) / 2;
      tt[lc[now]] = tt[rc[now]] = tt[now];
    }
  }
  long long query(int now, int l, int r, int ll, int rr, int T) {
    int mid = (l + r) / 2;
    long long ans = 0;
    if (l == ll && r == rr) {
      if (c[now] == 0)
        ans = solve(now, l, r, T), tt[now] = T;
      else {
        ans = query(lc[now], l, mid, ll, mid, T) +
              query(rc[now], mid + 1, r, mid + 1, rr, T);
        c[now] = 0, tt[now] = T;
      }
      return ans;
    }
    pushdown(now, l, r);
    if (rr <= mid)
      ans = query(lc[now], l, mid, ll, rr, T);
    else if (ll > mid)
      ans = query(rc[now], mid + 1, r, ll, rr, T);
    else
      ans = query(lc[now], l, mid, ll, mid, T) +
            query(rc[now], mid + 1, r, mid + 1, rr, T);
    if (c[lc[now]] == 0 && c[rc[now]] == 0 && tt[lc[now]] == tt[rc[now]])
      c[now] = 0, tt[now] = tt[lc[now]];
    else
      c[now] = 1, tt[now] = _min(tt[lc[now]], tt[rc[now]]);
    return ans;
  }
} t;
int main() {
  int n = read();
  for (int i = 1; i <= n; i++) {
    s[i] = read(), m[i] = read(), R[i] = read();
    s2[i] = s2[i - 1] + m[i];
  }
  t.bt(1, n);
  int m = read();
  for (int i = 1; i <= m; i++) {
    int T = read(), l = read(), r = read();
    put(t.query(1, 1, n, l, r, T)), puts("");
  }
  return 0;
}