e-olymp
Змагання

December 18 - 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

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані
10 10 955379886 619166003
0 0 0 0
Вихідні дані
7671393960
Автор С.Копеліович, С.Рогуленко