E. Маленькие пони и Lord Tirek
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Lord Tirek — кентавр и главный антагонист в последнем эпизоде четвертого сезона сериала «My Little Pony: Friendship Is Magic». В «Twilight's Kingdom» (часть 1), Tirek сбегает из Tartarus. Он высасывает ману из пони, чтобы стать сильнее.

Основная способность Tirek называется поглощение маны. С помощью нее Tirek может забрать всю ману у любого волшебного существа.

Рассмотрим упрощенную модель. Представим, что у нас есть n пони (пронумерованы от 1 до n). У каждого пони есть три атрибута:

  • si : количество маны в момент времени 0;
  • mi : максимально возможное количество маны;
  • ri : регенерация маны в единицу времени.

Lord Tirek выполняет m инструкций, каждая из которых характеризуется тремя целыми числами: ti, li, ri. Числа обозначают, что в момент времени ti Tirek использует свою основную способность, чтобы поглотить ману у пони с номерами от li до ri (обе границы включительно). Вам заданы все инструкции, которые выполняет Tirek, в хронологическом порядке. Для каждой из них выведите, сколько маны суммарно поглотит Tirek, выполняя эту инструкцию.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество пони. Каждая из следующих n строк содержит три целых числа: si, mi, ri (0 ≤ si ≤ mi ≤ 105; 0 ≤ ri ≤ 105), обозначающие характеристики текущего пони.

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество инструкций. Каждая из следующих m строк содержит три целых числа: ti, li, ri (0 ≤ ti ≤ 109; 1 ≤ li ≤ ri ≤ n), описывающих текущую инструкцию. Инструкции заданы в порядке строгого возрастания ti (все ti различны).

Выходные данные

Для каждой инструкции выведите в отдельной строке количество маны, которое поглотит Tirek, выполнив эту инструкцию.

Примеры
Входные данные
5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5
Выходные данные
25
58
Примечание

Изначально у каждого пони 0 маны. Во время первой инструкции каждый пони имеет 5 маны, таким образом Tirek получает 25 маны в сумме. Каждый пони будет иметь 0 маны после первой инструкции.

Во время второй инструкции пони 3 имеет 14 маны, а у остальных пони количество маны равно их mi.