Little Pony and Lord Tirek

3000ms

262144K

Description:

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.

$\text{[math]}$

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:

s_i : amount of mana that the pony has at time 0;
m_i : maximum mana that the pony can have;
r_i : mana regeneration per unit time.

Lord Tirek will do m instructions, each of them can be described with three integers: t_i, l_i, r_i. The instruction means that at time t_i, Tirek will use Absorb Mana on ponies with numbers from l_i to r_i (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 ≤ 10⁵) — the number of ponies. Each of the next n lines contains three integers s_i, m_i, r_i (0 ≤ s_i ≤ m_i ≤ 10⁵; 0 ≤ r_i ≤ 10⁵), describing a pony.

The next line contains an integer m (1 ≤ m ≤ 10⁵) — the number of instructions. Each of the next m lines contains three integers t_i, l_i, r_i (0 ≤ t_i ≤ 10⁹; 1 ≤ l_i ≤ r_i ≤ n), describing an instruction of Lord Tirek. The instructions are given in strictly increasing order of t_i (all t_i are distinct).

Output:

For each instruction, output a single line which contains a single integer, the total mana absorbed in this instruction.

Sample Input:

Sample 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 m_i.

Informação

Provedor Codeforces

Código CF453E