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 onechar() {
  static const int BUFSIZE = 1 << 20;
  static char buf[BUFSIZE], *ptr = buf + BUFSIZE;
  if (ptr == buf + BUFSIZE) {
    fread(buf, 1, BUFSIZE, stdin);
    ptr = buf;
  }
  return *ptr++;
}
int nextint() {
  char c;
  while (!isdigit(c = onechar()) && c != '-')
    ;
  int ans = c == '-' ? 0 : c - '0', sign = c == '-' ? -1 : 1;
  while (isdigit(c = onechar())) ans = ans * 10 + c - '0';
  return ans * sign;
}
char nextchar() {
  char c;
  while (isspace(c = onechar()))
    ;
  return c;
}
string nextstring() {
  char c;
  string ret;
  while (!isspace(c = onechar())) ret += c;
  return ret;
}
template <typename T>
vector<T>& operator+=(vector<T>& v, const T& e) {
  v.push_back(e);
  return v;
}
template <typename T>
string tobin(T n) {
  string ret;
  do ret = char('0' + (n & 1)) + ret;
  while (n /= 2);
  return ret;
}
inline unsigned int nextbitperm(unsigned int mask) {
  unsigned int ile = __builtin_ctz(mask), t = ~(mask >> ile),
               q = __builtin_ctz(t);
  return ~(((((((t >> q) - 1) << 1) + 1) << ile) | ((1 << (ile)) - 1))
           << (q - 1));
}
class Num {
  static constexpr long long int MOD = 1000000007LL;
  long long val;

 public:
  long long int get() const { return val; }
  Num(long long int x = 0LL) : val(x) {}
  Num operator+(const Num& other) const { return (val + other.val) % MOD; }
  Num operator*(const Num& other) const { return val * other.val % MOD; }
  Num operator-(const Num& other) const {
    return (val - other.val + MOD) % MOD;
  }
  static Num power(const Num& num, long long int k) {
    Num res = 1LL, curr = num;
    while (k) {
      if (k & 1LL) res = res * curr;
      curr = curr * curr;
      k /= 2LL;
    }
    return res;
  }
  Num power(long long int k) const { return power(*this, k); }
  Num operator/(const Num& other) const {
    Num res = (*this) * power(other, MOD - 2);
    assert((res * other).get() == this->get());
    return res;
  }
};
const long long int inf = 4000000000000000000LL;
struct Three {
  long long int time;
  long long int sumMax;
  long long int reg;
  bool operator<(const Three& other) const { return time < other.time; }
};
Three add(Three t1, Three t2) {
  return {0, t1.sumMax + t2.sumMax, t1.reg + t2.reg};
}
struct Tree {
  struct Node {
    vector<Three> v;
    Node() { v.push_back({0, 0, 0}); }
    Node(int m, int r) {
      if (r == 0)
        v.push_back({0, 0, 0});
      else {
        long long int t = m / r + 1;
        v.push_back({0, 0, r});
        v.push_back({t, m, 0});
      }
    }
    void merge(const Node& n1, const Node& n2) {
      ;
      for (Three th : n1.v)
        ;
      ;
      for (Three th : n2.v)
        ;
      ;
      v.push_back({0, 0, n1.v[0].reg + n2.v[0].reg});
      for (int i1 = 1, i2 = 1; i1 < n1.v.size() || i2 < n2.v.size();) {
        long long int t1 = i1 == n1.v.size() ? inf : n1.v[i1].time;
        long long int t2 = i2 == n2.v.size() ? inf : n2.v[i2].time;
        Three res;
        if (t1 < t2) {
          res = add(n1.v[i1], n2.v[i2 - 1]);
          res.time = t1;
          i1++;
        } else {
          res = add(n1.v[i1 - 1], n2.v[i2]);
          res.time = t2;
          i2++;
        }
        v.push_back(res);
      }
    }
  };
  vector<Node> tree;
  int N;
  Tree(vector<pair<int, int> > init) {
    int n = init.size();
    for (N = 1; N < n; N *= 2)
      ;
    tree.resize(2 * N);
    for (int i = 0; i < n; i++) {
      tree[N + i] = Node(init[i].first, init[i].second);
    }
    for (int i = N - 1; i >= 1; i--) {
      int c1 = 2 * i, c2 = 2 * i + 1;
      tree[i].merge(tree[c1], tree[c2]);
    }
    for (int i = 0; i < 2 * N; i++) {
      ;
      for (Three th : tree[i].v)
        ;
      ;
    }
  }
  long long int computeOne(int index, const Node& node, long long int t0) {
    int ind = upper_bound(node.v.begin(), node.v.end(), Three{t0, 0LL, 0LL}) -
              node.v.begin();
    ind--;
    assert(ind >= 0);
    ;
    for (Three th : node.v)
      ;
    ;
    ;
    return t0 * node.v[ind].reg + node.v[ind].sumMax;
  }
  long long int compute(int beg, int end, long long int t0) {
    beg += N;
    end += N;
    long long int res = 0;
    while (beg <= end) {
      if (beg & 1) {
        res += computeOne(beg, tree[beg], t0);
        beg++;
      }
      if (!(end & 1)) {
        res += computeOne(end, tree[end], t0);
        end--;
      }
      beg /= 2;
      end /= 2;
    }
    return res;
  }
};
struct Interv {
  int beg, end;
  long long int last;
  bool operator<(const Interv& other) const { return beg < other.beg; }
};
int main() {
  ios_base::sync_with_stdio(false);
  int N;
  scanf("%d", &N);
  vector<int> start(N);
  vector<pair<int, int> > param(N);
  for (int i = 0; i < N; i++) {
    scanf("%d %d %d", &start[i], &param[i].first, &param[i].second);
  }
  Tree tree(param);
  set<Interv> S;
  S.insert({0, N - 1, -1});
  auto split = [&S](set<Interv>::iterator it, int beg0, int whichRet) {
    assert(it != S.end());
    ;
    int b = it->beg, e = it->end, last = it->last;
    S.erase(it);
    set<Interv>::iterator it1 = S.end(), it2 = S.end();
    if (b < beg0) {
      bool bb;
      tie(it1, bb) = S.insert({b, beg0 - 1, last});
      assert(bb);
    }
    if (beg0 <= e) {
      bool bb;
      tie(it2, bb) = S.insert({beg0, e, last});
      assert(bb);
    }
    auto ret = whichRet == 1 ? it1 : it2;
    assert(ret != S.end());
    return ret;
  };
  ;
  int M;
  scanf("%d", &M);
  for (int qu = 0; qu < M; qu++) {
    int t0, beg0, end0;
    scanf("%d %d %d", &t0, &beg0, &end0);
    beg0--;
    end0--;
    for (auto it : S)
      ;
    ;
    Interv curr{beg0, end0, -1};
    auto it = S.upper_bound(curr);
    assert(S.size());
    assert(it != S.begin());
    it--;
    long long int result = 0LL;
    it = split(it, beg0, 2);
    bool loop = true;
    while (loop && it != S.end()) {
      ;
      if (it->end >= end0) {
        it = split(it, end0 + 1, 1);
        loop = false;
      }
      assert(it != S.end());
      if (it->last == -1) {
        for (int i = it->beg; i <= it->end; i++) {
          assert(i >= 0 && i < N);
          result +=
              min(1LL * t0 * param[i].second + start[i], 1LL * param[i].first);
        };
      } else {
        auto added = tree.compute(it->beg, it->end, t0 - (it->last));
        ;
        result += added;
      }
      auto it2 = it;
      it2++;
      S.erase(it);
      it = it2;
    }
    S.insert({beg0, end0, t0});
    cout << result << endl;
  }
  return 0;
}