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;
int t0[100100];
int maxt[100100];
int dt[100100];
long long ans[100100];
int t[100100];
int a[100100];
int b[100100];
pair<int, int> T[4 * 100100];
int tt[4 * 100100];
int lazy[4 * 100100];
void refresh(int init, int fim, int p) {
  if (tt[p] == 0) return;
  tt[p] = 0;
  T[p].first = T[p].second = lazy[p];
  if (init != fim) {
    tt[2 * p] = tt[2 * p + 1] = 1;
    lazy[2 * p] = lazy[2 * p + 1] = lazy[p];
  }
  lazy[p] = 0;
}
void update(int init, int fim, int p, int l, int r, int val) {
  refresh(init, fim, p);
  if (init > r || fim < l) return;
  if (init >= l && fim <= r) {
    lazy[p] = val;
    tt[p] = 1;
    refresh(init, fim, p);
    return;
  }
  int mid = (init + fim) / 2;
  update(init, mid, 2 * p, l, r, val);
  update(mid + 1, fim, 2 * p + 1, l, r, val);
  T[p].first = min(T[2 * p].first, T[2 * p + 1].first);
  T[p].second = max(T[2 * p].second, T[2 * p + 1].second);
}
pair<int, int> query(int init, int fim, int p, int l, int r) {
  refresh(init, fim, p);
  if (init > r || fim < l) return pair<int, int>((999999999), 0);
  if (init >= l && fim <= r) return T[p];
  int mid = (init + fim) / 2;
  pair<int, int> A = query(init, mid, 2 * p, l, r);
  pair<int, int> B = query(mid + 1, fim, 2 * p + 1, l, r);
  T[p].first = min(T[2 * p].first, T[2 * p + 1].first);
  T[p].second = max(T[2 * p].second, T[2 * p + 1].second);
  return pair<int, int>(min(A.first, B.first), max(A.second, B.second));
}
int aa;
int search(int init, int fim, int p, int pos, int val) {
  refresh(init, fim, p);
  if (init == fim) {
    if (T[p].first != val || T[p].second != val) {
      return 1;
    }
    aa = init;
    return 0;
  }
  int mid = (init + fim) / 2;
  if (pos < init) {
    refresh(init, mid, 2 * p);
    if (T[2 * p].first == T[2 * p].second && T[2 * p].first == val) {
      aa = mid;
      int ret = search(mid + 1, fim, 2 * p + 1, pos, val);
      if (ret == 0) aa = fim;
      return ret;
    }
    return search(init, mid, 2 * p, pos, val);
  }
  if (pos <= mid) {
    int u = search(init, mid, 2 * p, pos, val);
    if (u == 0) {
      aa = mid;
      int ret = search(mid + 1, fim, 2 * p + 1, pos, val);
      if (ret == 0) aa = fim;
      return ret;
    }
    return 1;
  }
  return search(mid + 1, fim, 2 * p + 1, pos, val);
}
vector<int> tree[4 * 100100];
vector<long long> sum_max[4 * 100100];
vector<long long> sum_dt[4 * 100100];
vector<long long> sum_t0[4 * 100100];
void build(int init, int fim, int p) {
  tree[p].clear();
  sum_max[p].clear();
  sum_dt[p].clear();
  sum_t0[p].clear();
  if (init == fim) {
    int u;
    if (dt[init] == 0) {
      u = (999999999);
    } else {
      int falta = maxt[init] - t0[init];
      u = falta / dt[init];
      if (falta % dt[init]) u++;
    }
    tree[p].push_back(u);
    ;
    sum_max[p].push_back(maxt[init]);
    sum_dt[p].push_back(dt[init]);
    sum_t0[p].push_back(t0[init]);
    return;
  }
  int mid = (init + fim) / 2;
  build(init, mid, 2 * p);
  build(mid + 1, fim, 2 * p + 1);
  int pa = 0, push_back = 0;
  int ta = mid - init + 1, tb = fim - mid;
  int cur = 0;
  while (pa + push_back <= fim - init) {
    int pick;
    if (pa == ta)
      pick = 1;
    else if (push_back == tb)
      pick = 0;
    else if (tree[2 * p][pa] < tree[2 * p + 1][push_back])
      pick = 0;
    else
      pick = 1;
    if (pick == 0) {
      tree[p].push_back(tree[2 * p][pa]);
      sum_max[p].push_back(sum_max[2 * p][pa] -
                           (pa ? sum_max[2 * p][pa - 1] : 0));
      if (cur) sum_max[p][cur] += sum_max[p][cur - 1];
      sum_dt[p].push_back(sum_dt[2 * p][pa] - (pa ? sum_dt[2 * p][pa - 1] : 0));
      if (cur) sum_dt[p][cur] += sum_dt[p][cur - 1];
      sum_t0[p].push_back(sum_t0[2 * p][pa] - (pa ? sum_t0[2 * p][pa - 1] : 0));
      if (cur) sum_t0[p][cur] += sum_t0[p][cur - 1];
      pa++;
    } else {
      tree[p].push_back(tree[2 * p + 1][push_back]);
      sum_max[p].push_back(sum_max[2 * p + 1][push_back] -
                           (push_back ? sum_max[2 * p + 1][push_back - 1] : 0));
      if (cur) sum_max[p][cur] += sum_max[p][cur - 1];
      sum_dt[p].push_back(sum_dt[2 * p + 1][push_back] -
                          (push_back ? sum_dt[2 * p + 1][push_back - 1] : 0));
      if (cur) sum_dt[p][cur] += sum_dt[p][cur - 1];
      sum_t0[p].push_back(sum_t0[2 * p + 1][push_back] -
                          (push_back ? sum_t0[2 * p + 1][push_back - 1] : 0));
      if (cur) sum_t0[p][cur] += sum_t0[p][cur - 1];
      push_back++;
    }
    cur++;
  }
}
long long query2(int init, int fim, int p, int l, int r, int tt) {
  if (init > r || fim < l) return 0;
  if (init >= l && fim <= r) {
    ;
    int low = 0, up = tree[p].size() - 1;
    int len = up;
    if (tree[p][up] <= tt) {
      ;
      return sum_max[p][up];
    }
    if (tree[p][0] > tt) {
      ;
      return sum_t0[p][up] + tt * sum_dt[p][up];
    }
    while (up - low) {
      int mid = (low + up + 1) / 2;
      if (tree[p][mid] <= tt)
        low = mid;
      else
        up = mid - 1;
    }
    long long ret = sum_max[p][up] + (sum_t0[p][len] - sum_t0[p][up]) +
                    (long long)tt * (sum_dt[p][len] - sum_dt[p][up]);
    ;
    ;
    return ret;
  }
  int mid = (init + fim) / 2;
  return query2(init, mid, 2 * p, l, r, tt) +
         query2(mid + 1, fim, 2 * p + 1, l, r, tt);
}
int main() {
  int n, q;
  scanf("%d", &n);
  vector<int> vv;
  for (int i = 0; i < n; i++) {
    scanf("%d%d%d", t0 + i, maxt + i, dt + i);
    vv.push_back(t0[i]);
    t0[i] = 0;
  }
  build(0, n - 1, 1);
  scanf("%d", &q);
  for (int i = 0; i < q; i++)
    scanf("%d%d%d", t + i, a + i, b + i), a[i]--, b[i]--;
  update(0, n - 1, 1, 0, n - 1, q);
  for (int i = q - 1; i >= 0; i--) {
    int u = a[i];
    while (u <= b[i]) {
      int low = u, up = b[i];
      aa = u;
      search(0, n - 1, 1, u, query(0, n - 1, 1, u, u).first);
      aa = min(aa, b[i]);
      up = aa;
      ;
      int y = query(0, n - 1, 1, u, up).first;
      if (y != q) {
        ;
        ans[y] += query2(0, n - 1, 1, u, up, t[y] - t[i]);
      }
      u = up + 1;
    }
    update(0, n - 1, 1, a[i], b[i], i);
  }
  for (int i = 0; i < n; i++) t0[i] = vv[i];
  build(0, n - 1, 1);
  int u = 0;
  while (u < n) {
    int low = u, up = n - 1;
    aa = u;
    search(0, n - 1, 1, u, query(0, n - 1, 1, u, u).first);
    up = aa;
    int y = query(0, n - 1, 1, u, up).first;
    if (y != q) {
      ;
      ans[y] += query2(0, n - 1, 1, u, up, t[y]);
    }
    u = up + 1;
  }
  for (int i = 0; i < q; i++) printf("%I64d\n", ans[i]);
}