RMQ
RMQ
Задан массив из n целых чисел и m запросов вида: найти минимум на отрезке с концами li
, ri
.
Входные данные
Состоит из t тестов. Каждый тест задаётся числами n, m, a, b (1 ≤ n ≤ 25000, 1 ≤ a, b ≤ 109
), где n - размер массива, m - число запросов. Массив и запросы нужно получить следующим образом: выпишем последовательность чисел a·1 + b, a·2 + b, ..., a·(n + 2·m) + b, взятых по модулю 232
. Первые n чисел последовательности - элементы массива, числа с n + 1 по n + 2 · m, взятые по модулю n, образуют m пар чисел li
- 1, ri
- 1 - запросы.
Ввод заканчивается строкой 0 0 0 0.
Сумма n по всем наборам тестов не превосходит 109
, cумма m по всем наборам тестовых данных не превосходит 20000000.
Выходные данные
Для каждого теста выведите в отдельной строке сумму по всем запросам.
Пояснение к примеру
Массив: 1574545889 2529925775 3485305661 145718251 1101098137 2056478023 3011857909 3967237795 627650385 1583030271
Запросы:
8 4
4 10
6 2
8 8
4 10
6 6
2 8
4 10
10 6
2 8
10 10 955379886 619166003 0 0 0 0
7671393960