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 maxn = 1e5, maxm = 1e5, max0 = 1e6;
struct data {
  int s, m, r;
};
data a[maxn + 5];
int n, m;
void init() {
  scanf("%d", &n);
  for (int i = (0), _end_ = (n); i != _end_; ++i)
    scanf("%d%d%d", &a[i].s, &a[i].m, &a[i].r);
}
struct que {
  int l, r, t;
  int ret;
  que() {}
  que(const int &_l, const int &_r, const int &_t, const int &_ret)
      : l(_l), r(_r), t(_t), ret(_ret) {}
  friend bool operator<(const que &first, const que &second) {
    return first.t < second.t;
  }
};
long long ans[maxm + 5];
que q0[max0 + 5], q1[max0 + 5];
int cnt0 = 0, cnt1 = 0;
struct node {
  bool has_label;
  int label;
  node *c[2];
  node() : has_label(0), label(-2) { memset(c, 0, sizeof c); }
  void push_down();
};
node node_memory[max0 + 5];
int node_cur = 0;
node *rt = NULL;
node *get() { return node_memory + (node_cur++); }
void node::push_down() {
  if (label != -2) {
    for (int i = (0), _end_ = (2); i != _end_; ++i) {
      if (!c[i]) c[i] = get();
      c[i]->label = label;
      c[i]->has_label = 1;
    }
    label = -2;
  }
}
pair<pair<int, int>, int> all_seg[maxn + 5];
int all_seg_cnt = 0;
void clear_all_label(node *rt, const int &l, const int &r) {
  if (rt == NULL || !rt->has_label) return;
  rt->has_label = 0;
  if (rt->label != -2) {
    all_seg[all_seg_cnt++] = make_pair(make_pair(l, r), rt->label);
    rt->label = 0;
    return;
  }
  int mid = (l + r) >> 1;
  clear_all_label(rt->c[0], l, mid);
  clear_all_label(rt->c[1], mid, r);
}
void insert(node *&rt, const int &first, const int &second, const int &z,
            const int &l = 0, const int &r = maxn) {
  if (rt == NULL) rt = get();
  if (first <= l && r <= second) {
    clear_all_label(rt, l, r);
    rt->has_label = 1, rt->label = z;
    return;
  }
  rt->has_label = 1;
  rt->push_down();
  int mid = (l + r) >> 1;
  if (first < mid) insert(rt->c[0], first, second, z, l, mid);
  if (second > mid) insert(rt->c[1], first, second, z, mid, r);
}
void prepare() {
  insert(rt, 0, n, -1);
  scanf("%d", &m);
  for (int i = (0), _end_ = (m); i != _end_; ++i) {
    static int l, r, t;
    scanf("%d%d%d", &t, &l, &r), --l;
    all_seg_cnt = 0;
    insert(rt, l, r, t);
    for (int j = 0; j < all_seg_cnt;) {
      const int &l = all_seg[j].first.first, &val = all_seg[j].second;
      int r;
      while (j < all_seg_cnt && all_seg[j].second == val)
        r = all_seg[j++].first.second;
      if (val != -1)
        q0[cnt0++] = que(l, r, t - val, i);
      else
        q1[cnt1++] = que(l, r, t, i);
    }
  }
}
pair<int, int> ev[maxn + 5];
int evn = 0;
long long sum0[maxn + 5], sum1[maxn + 5];
void add(const int &first, const int &second, long long *sum) {
  for (int i = first + 1; i <= n; i += i & -i) sum[i] += second;
}
long long query_pre(const int &first, long long *sum) {
  long long ret = 0;
  for (int i = first; i > 0; i -= i & -i) ret += sum[i];
  return ret;
}
long long query(const int &l, const int &r, const int &t) {
  long long tmp0 = query_pre(r, sum0) - query_pre(l, sum0),
            tmp1 = query_pre(r, sum1) - query_pre(l, sum1);
  return tmp1 + tmp0 * t;
}
void work(que *q1, const int &cnt1) {
  memset(sum0, 0, sizeof sum0);
  memset(sum1, 0, sizeof sum1);
  for (int i = (0), _end_ = (n); i != _end_; ++i)
    add(i, a[i].r, sum0), add(i, a[i].s, sum1);
  evn = 0;
  for (int i = (0), _end_ = (n); i != _end_; ++i)
    if (a[i].r)
      ev[evn++] = make_pair((a[i].m - a[i].s + a[i].r - 1) / a[i].r, i);
  sort(ev, ev + evn);
  sort(q1, q1 + cnt1);
  int j = 0;
  for (int i = (0), _end_ = (cnt1); i != _end_; ++i) {
    while (j < evn && ev[j].first <= q1[i].t) {
      add(ev[j].second, -a[ev[j].second].r, sum0);
      add(ev[j].second, a[ev[j].second].m - a[ev[j].second].s, sum1);
      ++j;
    }
    ans[q1[i].ret] += query(q1[i].l, q1[i].r, q1[i].t);
  }
}
void solve() {
  memset(ans, 0, sizeof ans);
  work(q1, cnt1);
  for (int i = (0), _end_ = (n); i != _end_; ++i) a[i].s = 0;
  work(q0, cnt0);
}
void output() {
  for (int i = (0), _end_ = (m); i != _end_; ++i) printf("%I64d\n", ans[i]);
}
int main() {
  init();
  prepare();
  solve();
  output();
  return 0;
}