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 = 1e9 + 100500;
const int maxn = 100500;
struct node {
  int id;
  int x, y;
  long long add, add_progr;
  long long val;
  node *l, *r, *p;
  node() {}
  node(int id) : id(id), x(0), y(rand()), l(r = p = NULL) {
    add = add_progr = val = 0;
  }
  bool isl() const { return p && p->l == this; }
  bool isr() const { return p && p->r == this; }
};
inline node *push(node *t) {
  if (t) {
    t->val += t->add + t->add_progr * t->x;
    if (t->l) {
      t->l->add += t->add;
      t->l->add_progr += t->add_progr;
    }
    if (t->r) {
      t->r->add += t->add;
      t->r->add_progr += t->add_progr;
    }
    t->add = t->add_progr = 0;
  }
  return t;
}
inline node *norm(node *t) {
  if (t) {
    if (t->l) {
      t->l->p = t;
    }
    if (t->r) {
      t->r->p = t;
    }
  }
  return t;
}
void split(node *t, node *&l, node *&r, int x) {
  if (!t) return (void)(l = r = NULL);
  push(t);
  if (x < t->x)
    split(t->l, l, t->l, x), r = t;
  else
    split(t->r, t->r, r, x), l = t;
  t->p = NULL;
  norm(t);
}
node *merge(node *l, node *r) {
  if (!l) return r;
  if (!r) return l;
  push(l);
  push(r);
  if (r->y > l->y) {
    r->l = merge(l, r->l);
    return norm(r);
  } else {
    l->r = merge(l->r, r);
    return norm(l);
  }
}
void push_way_up(node *t) {
  if (t->p) {
    push_way_up(t->p);
  }
  push(t);
}
void split(node *t, node *&l, node *&r) {
  if (!t) return (void)(l = r = NULL);
  push_way_up(t);
  node *ll = t, *lr = t->r;
  if (lr) lr->p = NULL;
  t->r = NULL;
  norm(lr);
  norm(ll);
  bool lturn = true;
  while (t->p) {
    if (t->isl()) {
      t = t->p;
      if (lturn) {
        ll->p = NULL;
        t->l = lr;
      }
      lturn = 0;
      lr = t;
    } else {
      t = t->p;
      if (!lturn) {
        lr->p = NULL;
        t->r = ll;
      }
      lturn = 1;
      ll = t;
    }
    norm(t);
  }
  l = ll;
  r = lr;
}
int q;
node *nodes[maxn];
node *t;
struct query {
  int id;
  int t;
  int l, r;
  bool operator<(const query &q) const { return t < q.t; }
} queries[maxn];
set<query> curq;
struct event {
  int x;
  int t, id;
  bool operator<(const event &e) const {
    if (x != e.x) return x < e.x;
    return t < e.t;
  }
};
int n;
int st[maxn], reg[maxn], mx[maxn];
void scan() {
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) scanf("%d%d%d", &st[i], &mx[i], &reg[i]);
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); ++i) {
    int l, r, t;
    scanf("%d%d%d", &t, &l, &r);
    queries[i] = {i, t, l - 1, r - 1};
  }
}
void out(node *t) {
  if (t) {
    out(t->l);
    cout << t->id << ": " << t->x << endl;
    out(t->r);
  }
}
void push_all(node *t) {
  return;
  if (t) {
    push(t);
    push_all(t->l);
    push_all(t->r);
  }
}
void move_query(int id, int nx) {
  push_all(t);
  if (nodes[id]->x != 0) {
    node *l, *r;
    split(nodes[id], l, r);
    nodes[id]->x = inf;
    split(l, l, nodes[id], inf - 1);
    assert(nodes[id]->id == id);
    t = merge(l, r);
  }
  if (nx != 0) {
    nodes[id]->x = nx;
    node *l, *r;
    split(t, l, r, nx);
    t = merge(merge(l, nodes[id]), r);
  }
  push_all(t);
}
void add_query(int id) {
  auto it = curq.insert(queries[id]).first;
  assert(it != curq.begin());
  auto itp = it;
  ++itp;
  assert(itp != curq.end());
  if (itp->id != -1) {
    move_query(itp->id, itp->t - queries[id].t);
  }
  -- --itp;
  move_query(id, queries[id].t - itp->t);
}
void remove_query(int id) {
  auto it = curq.lower_bound(queries[id]);
  assert(it != curq.begin() && it != curq.end() && it->id == id);
  move_query(id, 0);
  auto itp = it;
  ++itp;
  assert(itp != curq.end());
  auto itpp = itp;
  -- --itpp;
  if (itp->id != -1) {
    move_query(itp->id, itp->t - itpp->t);
  }
  curq.erase(it);
}
void add_pony(int id) {
  if (curq.size() == 2u) return;
  int fq = next(curq.begin())->id;
  assert(nodes[fq]->x >= inf);
  nodes[fq]->val +=
      min(st[id] + (long long)reg[id] * queries[fq].t, (long long)mx[id]) -
      mx[id];
  int max_alive = reg[id] ? mx[id] / reg[id] : (inf - 1);
  push_all(t);
  node *l, *r;
  split(t, l, r, max_alive);
  if (l) l->add_progr += reg[id];
  if (r) r->add += mx[id];
  push_all(l);
  push_all(r);
  t = merge(l, r);
}
void solve() {
  for (int i = 0; i < (int)(q); ++i) {
    nodes[i] = new node(i);
  }
  vector<event> evs;
  for (int i = 0; i < (int)(q); ++i) {
    evs.push_back({queries[i].l, 0, queries[i].id});
    evs.push_back({queries[i].r, 2, queries[i].id});
  }
  for (int i = 0; i < (int)(n); ++i) {
    evs.push_back({i, 1, 0});
  }
  sort((evs).begin(), (evs).end());
  curq.insert({-1, -inf, 0, 0});
  curq.insert({-1, inf, 0, 0});
  for (auto e : evs) {
    if (e.t == 0) {
      add_query(e.id);
    } else if (e.t == 2) {
      remove_query(e.id);
    } else {
      add_pony(e.x);
    }
  }
  for (int i = 0; i < (int)(q); ++i) {
    push(nodes[i]);
    cout << nodes[i]->val << "\n";
  }
}
int main() {
  scan();
  solve();
  return 0;
}