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;
struct Tree {
  long long change, fix;
  Tree *son[2];
  Tree() {
    change = fix = 0;
    son[0] = son[1] = 0;
  }
} tree[9000050], *st;
struct Tnode {
  int len, times, size;
  long long answer;
  Tnode *father, *son[2];
  Tnode() {}
  Tnode(Tnode *f, int t, int s) {
    times = t;
    size = s;
    len = answer = 0;
    father = f;
    son[0] = son[1] = 0;
  }
} memory[100050], *root;
struct Tedge {
  int to, flag, next;
} edge[200050];
struct Data {
  int s, m, r, t;
} data[100050];
struct Ask {
  int t, l, r;
} ask[100050];
int now, vs, tt, first[100050];
long long answer[100050];
int Rand() { return (rand() << 15) | rand(); }
void Addedge(int x, int y, int z) {
  edge[++now].to = y;
  edge[now].flag = z;
  edge[now].next = first[x];
  first[x] = now;
  return;
}
void Build_ST(Tree *current) {
  if (!current->son[0]) {
    tree[++tt] = Tree();
    current->son[0] = &tree[tt];
  }
  if (!current->son[1]) {
    tree[++tt] = Tree();
    current->son[1] = &tree[tt];
  }
  return;
}
long long Ask(Tree *current, int nowleft, int nowright, int askleft,
              int askright) {
  int mid = (nowleft + nowright) >> 1;
  Build_ST(current);
  if (nowright < askleft || askright < nowleft) {
    return 0;
  }
  if (askleft <= nowleft && nowright <= askright) {
    return current->change * askleft + current->fix;
  }
  return Ask(current->son[0], nowleft, mid, askleft, askright) +
         Ask(current->son[1], mid + 1, nowright, askleft, askright) +
         current->change * askleft + current->fix;
}
void Change(Tree *current, int nowleft, int nowright, int askleft, int askright,
            int change) {
  int mid = (nowleft + nowright) >> 1;
  Build_ST(current);
  if (nowright < askleft || askright < nowleft) {
    return;
  }
  if (askleft <= nowleft && nowright <= askright) {
    current->change += change;
    return;
  }
  Change(current->son[0], nowleft, mid, askleft, askright, change);
  Change(current->son[1], mid + 1, nowright, askleft, askright, change);
  return;
}
void Fix(Tree *current, int nowleft, int nowright, int askleft, int askright,
         int fix) {
  int mid = (nowleft + nowright) >> 1;
  Build_ST(current);
  if (nowright < askleft || askright < nowleft) {
    return;
  }
  if (askleft <= nowleft && nowright <= askright) {
    current->fix += fix;
    return;
  }
  Fix(current->son[0], nowleft, mid, askleft, askright, fix);
  Fix(current->son[1], mid + 1, nowright, askleft, askright, fix);
  return;
}
void Update(Tnode *current) {
  if (!current) {
    return;
  }
  current->size = 1;
  if (current->son[0]) {
    current->size += current->son[0]->size;
  }
  if (current->son[1]) {
    current->size += current->son[1]->size;
  }
  return;
}
void Rotate(Tnode *current, int flag) {
  current->father->son[flag ^ 1] = current->son[flag];
  if (current->son[flag]) {
    current->son[flag]->father = current->father;
  }
  current->son[flag] = current->father;
  if (current->father->father) {
    current->father->father
        ->son[current->father->father->son[0] != current->father] = current;
  }
  current->father = current->father->father;
  current->son[flag]->father = current;
  Update(current->son[flag]);
  return;
}
void Splay(Tnode *current, Tnode *target) {
  while (current->father != target) {
    if (current->father->father == target) {
      Rotate(current, current->father->son[1] != current);
    } else if (current->father->father->son[0] == current->father &&
               current->father->son[0] == current) {
      Rotate(current->father, 1);
      Rotate(current, 1);
    } else if (current->father->father->son[1] == current->father &&
               current->father->son[1] == current) {
      Rotate(current->father, 0);
      Rotate(current, 0);
    } else {
      Rotate(current, current->father->son[1] != current);
      Rotate(current, current->father->son[1] != current);
    }
  }
  Update(current);
  if (!target) {
    root = current;
  }
  return;
}
void Find(int ask, Tnode *target) {
  Tnode *current = root;
  while (current) {
    if (current->son[0]) {
      if (ask == current->son[0]->size + 1) {
        break;
      }
    } else if (ask == 1) {
      break;
    }
    if (current->son[0] && ask < current->son[0]->size + 1) {
      current = current->son[0];
    } else {
      ask--;
      if (current->son[0]) {
        ask -= current->son[0]->size;
      }
      current = current->son[1];
    }
  }
  Splay(current, target);
  return;
}
void Bigger(int ask, Tnode *target) {
  Tnode *current = root, *best = 0;
  while (current) {
    if (current->times > ask) {
      best = current;
      current = current->son[0];
    } else {
      current = current->son[1];
    }
  }
  Splay(best, target);
  return;
}
void Smaller(int ask, Tnode *target) {
  Tnode *current = root, *best = 0;
  while (current) {
    if (current->times < ask) {
      best = current;
      current = current->son[1];
    } else {
      current = current->son[0];
    }
  }
  Splay(best, target);
  return;
}
void Find_Left(Tnode *current) {
  while (true) {
    if (!current->son[0]) {
      break;
    }
    current = current->son[0];
  }
  Splay(current, 0);
  return;
}
void Find_Right(Tnode *current) {
  while (true) {
    if (!current->son[1]) {
      break;
    }
    current = current->son[1];
  }
  Splay(current, 0);
  return;
}
int main() {
  int n, m, i, pointer, temp, flag, need;
  Tnode *current;
  srand((unsigned)time(0));
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d%d%d", &data[i].s, &data[i].m, &data[i].r);
    if (data[i].r > 0) {
      data[i].t = data[i].m / data[i].r;
      if (data[i].m % data[i].r != 0) {
        data[i].t++;
      }
    } else {
      data[i].m = 0;
    }
  }
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d", &ask[i].t, &ask[i].l, &ask[i].r);
    Addedge(ask[i].l, i, 0);
    Addedge(ask[i].r, i, 2);
  }
  tree[++tt] = Tree();
  st = &tree[tt];
  memory[++vs] = Tnode(0, -1111111111, 2);
  root = &memory[vs];
  memory[++vs] = Tnode(root, 1111111111, 1);
  root->son[1] = &memory[vs];
  for (i = 1; i <= n; i++) {
    for (pointer = first[i]; pointer; pointer = edge[pointer].next) {
      temp = edge[pointer].to;
      flag = edge[pointer].flag;
      if (flag != 0) {
        continue;
      }
      Smaller(ask[temp].t, 0);
      Bigger(ask[temp].t, root);
      memory[++vs] = Tnode(root->son[1], ask[temp].t, 1);
      root->son[1]->son[0] = &memory[vs];
      Update(root->son[1]);
      Update(root);
      current = root->son[1]->son[0];
      Splay(current, 0);
      current->len = ask[temp].t;
      if (current->son[0]->size > 1) {
        Find_Right(root->son[0]);
        current->len -= root->times;
      }
      current->answer -= Ask(st, 0, 1000000000, current->len, current->len);
      Splay(current, 0);
      if (current->son[1]->size > 1) {
        Find_Left(root->son[1]);
        root->answer += Ask(st, 0, 1000000000, root->len, root->len);
        root->len = root->times - current->times;
        root->answer -= Ask(st, 0, 1000000000, root->len, root->len);
      }
    }
    if (root->size > 2) {
      Find(2, 0);
      root->answer += data[i].s;
      root->answer += Ask(st, 0, 1000000000, root->len, root->len);
      if (data[i].r > 0) {
        need = (data[i].m - data[i].s) / data[i].r;
        if ((data[i].m - data[i].s) % data[i].r != 0) {
          need++;
        }
        if (root->times < need) {
          root->answer += root->times * data[i].r;
        } else {
          root->answer += data[i].m - data[i].s;
        }
      }
    }
    if (data[i].t >= 1) {
      Change(st, 0, 1000000000, 0, data[i].t - 1, data[i].r);
    }
    Fix(st, 0, 1000000000, data[i].t, 1000000000, data[i].m);
    if (root->size > 2) {
      Find(2, 0);
      root->answer -= Ask(st, 0, 1000000000, root->len, root->len);
    }
    for (pointer = first[i]; pointer; pointer = edge[pointer].next) {
      temp = edge[pointer].to;
      flag = edge[pointer].flag;
      if (flag != 2) {
        continue;
      }
      Smaller(ask[temp].t, 0);
      Bigger(ask[temp].t, root);
      current = root->son[1]->son[0];
      Splay(current, 0);
      if (current->son[1]->size > 1) {
        Find_Left(current->son[1]);
        root->answer += Ask(st, 0, 1000000000, root->len, root->len);
        root->len += current->len;
        root->answer -= Ask(st, 0, 1000000000, root->len, root->len);
      }
      current->answer += Ask(st, 0, 1000000000, current->len, current->len);
      answer[temp] = current->answer;
      Smaller(ask[temp].t, 0);
      Bigger(ask[temp].t, root);
      root->son[1]->son[0] = 0;
      Update(root->son[1]);
      Update(root);
    }
  }
  for (i = 1; i <= m; i++) {
    printf("%I64d\n", answer[i]);
  }
  return 0;
}