G. Функции на отрезках
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив f из n функций. Функция fi(x), где 1 ≤ i ≤ n, характеризуется следующими параметрами: x1, x2, y1, a, b, y2, и принимает значения следующим образом:

  • y1, если x ≤ x1.
  • a·x + b, если x1 < x ≤ x2.
  • y2, если x > x2.
Даны m запросов. Каждый запрос определяется тройкой чисел l, r и x. Для запроса с номером i, где 1 ≤ i ≤ m, требуется посчитать сумму всех fj(xi) для l ≤ j ≤ r. Значение xi вычисляется как xi = (x + last) mod 109, где last - ответ за запрос с номером i - 1. При i = 1 значение last равно 0.
Входные данные

В первой строке дано целое число n (1 ≤ n ≤ 75000).

Каждая из следующих n сток содержит шесть целых чисел: x1, x2, y1, a, b, y2 (0 ≤ x1 < x2 ≤ 2·105, 0 ≤ y1, y2 ≤ 109, 0 ≤ a, b ≤ 104).

В следующей строке дано целое число m (1 ≤ m ≤ 500000).

Каждая из следующих m строк содержит три целых числа: l, r и x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109).

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

Выведите для каждого запроса ответ на него в отдельной строке.

Примеры
Входные данные
1
1 2 1 4 5 10
1
1 1 2
Выходные данные
13
Входные данные
3
2 5 1 1 1 4
3 6 8 2 5 7
1 3 5 1 4 10
3
1 3 3
2 3 2
1 2 5
Выходные данные
19
17
11