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>
struct sFTree {
  int l, r;
  int pl, pr;
  int time;
  long long left;
  long long right;
} fTree[200009];
int fTreeSize = 0;
int FBuildTree(int l, int r) {
  int cur = ++fTreeSize;
  fTree[cur].l = l;
  fTree[cur].r = r;
  if (l < r) {
    fTree[cur].pl = FBuildTree(l, (l + r) / 2);
    fTree[cur].pr = FBuildTree((l + r) / 2 + 1, r);
  } else {
    fTree[cur].left = fTree[cur].right = l;
  }
  return cur;
}
int GetLeftBorder(int i, int cur) {
  int ans = 0;
  while (cur) {
    ans += fTree[cur].left;
    if (i <= fTree[fTree[cur].pl].r)
      cur = fTree[cur].pl;
    else
      cur = fTree[cur].pr;
  }
  return ans;
}
void UpdLeftBorder(int l, int r, int delta, int cur) {
  if (l <= fTree[cur].l && r >= fTree[cur].r) {
    fTree[cur].left += delta;
    return;
  }
  if (l <= fTree[fTree[cur].pl].r && fTree[fTree[cur].pl].l <= r)
    UpdLeftBorder(l, r, delta, fTree[cur].pl);
  if (l <= fTree[fTree[cur].pr].r && fTree[fTree[cur].pr].l <= r)
    UpdLeftBorder(l, r, delta, fTree[cur].pr);
}
int GetRightBorder(int i, int cur) {
  int ans = 0;
  while (cur) {
    ans += fTree[cur].right;
    if (i <= fTree[fTree[cur].pl].r)
      cur = fTree[cur].pl;
    else
      cur = fTree[cur].pr;
  }
  return ans;
}
void UpdRightBorder(int l, int r, int delta, int cur) {
  if (l <= fTree[cur].l && r >= fTree[cur].r) {
    fTree[cur].right += delta;
    return;
  }
  if (l <= fTree[fTree[cur].pl].r && fTree[fTree[cur].pl].l <= r)
    UpdRightBorder(l, r, delta, fTree[cur].pl);
  if (l <= fTree[fTree[cur].pr].r && fTree[fTree[cur].pr].l <= r)
    UpdRightBorder(l, r, delta, fTree[cur].pr);
}
struct sSTree {
  int l, r;
  int pl, pr;
  long long bot;
  long long top;
} sTree[2000009];
int sTreeSize = 0;
int SBuildTree(int l, int r) {
  int cur = ++sTreeSize;
  sTree[cur].l = l;
  sTree[cur].r = r;
  if (l < r) {
    sTree[cur].pl = SBuildTree(l, (l + r) / 2);
    sTree[cur].pr = SBuildTree((l + r) / 2 + 1, r);
  }
  return cur;
}
int Add(int i, long long a, long long b, int cur) {
  int tmp = ++sTreeSize;
  sTree[tmp] = sTree[cur];
  cur = tmp;
  if (sTree[cur].l == sTree[cur].r) {
    sTree[cur].bot += a;
    sTree[cur].top += b;
  } else {
    if (i <= sTree[sTree[cur].pl].r)
      sTree[cur].pl = Add(i, a, b, sTree[cur].pl);
    else
      sTree[cur].pr = Add(i, a, b, sTree[cur].pr);
    sTree[cur].bot = sTree[sTree[cur].pl].bot + sTree[sTree[cur].pr].bot;
    sTree[cur].top = sTree[sTree[cur].pl].top + sTree[sTree[cur].pr].top;
  }
  return cur;
}
long long GetBot(int l, int r, int cur) {
  if (l <= sTree[cur].l && r >= sTree[cur].r) return sTree[cur].bot;
  long long ans = 0;
  if (l <= sTree[sTree[cur].pl].r && sTree[sTree[cur].pl].l <= r)
    ans += GetBot(l, r, sTree[cur].pl);
  if (l <= sTree[sTree[cur].pr].r && sTree[sTree[cur].pr].l <= r)
    ans += GetBot(l, r, sTree[cur].pr);
  return ans;
}
long long GetTop(int l, int r, int cur) {
  if (l <= sTree[cur].l && r >= sTree[cur].r) return sTree[cur].top;
  long long ans = 0;
  if (l <= sTree[sTree[cur].pl].r && sTree[sTree[cur].pl].l <= r)
    ans += GetTop(l, r, sTree[cur].pl);
  if (l <= sTree[sTree[cur].pr].r && sTree[sTree[cur].pr].l <= r)
    ans += GetTop(l, r, sTree[cur].pr);
  return ans;
}
int prevTime[100009];
bool used[100009];
int S[100009];
int M[100009];
int R[100009];
int roots[100009];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d %d %d", &S[i], &M[i], &R[i]);
  int fRoot = FBuildTree(1, n);
  roots[0] = SBuildTree(0, 100002);
  for (int i = 1; i <= n; i++) {
    if (R[i]) {
      int t = M[i] / R[i];
      roots[i] = Add(t, R[i], M[i], roots[i - 1]);
    } else {
      roots[i] = roots[i - 1];
    }
  }
  int m;
  scanf("%d", &m);
  while (m--) {
    int t, l, r;
    scanf("%d %d %d", &t, &l, &r);
    long long ans = 0;
    {
      int L, R;
      L = GetLeftBorder(l, fRoot);
      if (L < l) {
        R = GetRightBorder(l, fRoot);
        UpdRightBorder(L, l - 1, l - 1 - R, fRoot);
        UpdLeftBorder(l, R, l - L, fRoot);
        prevTime[l] = prevTime[L];
      }
      R = GetRightBorder(r, fRoot);
      if (R > r) {
        L = GetLeftBorder(r, fRoot);
        UpdLeftBorder(r + 1, R, r + 1 - L, fRoot);
        UpdRightBorder(L, r, r - R, fRoot);
        prevTime[r + 1] = prevTime[L];
      }
    }
    int i = l;
    while (i <= r) {
      if (!used[i]) {
        ans += (((long long)M[i]) < ((long long)S[i] + (long long)t * R[i])
                    ? ((long long)M[i])
                    : ((long long)S[i] + (long long)t * R[i]));
        UpdLeftBorder(i, i, l - i, fRoot);
        UpdRightBorder(i, i, r - i, fRoot);
        used[i] = true;
        i++;
      } else {
        int L = GetLeftBorder(i, fRoot);
        int R = GetRightBorder(i, fRoot);
        int dt = t - prevTime[L];
        if (dt > 100000) dt = 100003;
        ans +=
            (GetBot(dt, 100003, roots[R]) - GetBot(dt, 100003, roots[L - 1])) *
                (long long)dt +
            GetTop(0, dt - 1, roots[R]) - GetTop(0, dt - 1, roots[L - 1]);
        UpdLeftBorder(L, R, l - L, fRoot);
        UpdRightBorder(L, R, r - R, fRoot);
        i = R + 1;
      }
    }
    prevTime[l] = t;
    printf("%I64d\n", ans);
  }
}