Задан массив 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.
Выходные данные
Выведите для каждого запроса ответ на него в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
1 2 1 4 5 10
1
1 1 2
|
13
|
|
2
|
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
|