RMQ
Є масив з N цілих чисел та M запитів виду: знайти мінімум на відрізку з кінцями l_i, r_i.
Вхідні дані
Складається з T тестів. Кожен тест задається числами N, M, A, B (1 ≤ N ≤ 25000, 1 ≤ A, B ≤ 10^9), де N - розмір масиву, M - число запитів. Масив та запити потрібно отримати наступним чином: випишемо послідовність чисел A·1 + B, A·2 + B, ..., A·(N + 2·M) + B, взятих по модулю 2^32. Перші N чисел послідовності - елементи масиву, числа від N + 1 до N + 2·M, взяті за модулем N утворюють M пар чисел l_i - 1, r_i - 1 - запити.
Вхідні даін завершуються рядком 0 0 0 0.
Сума N по усім наборам тестів не перевищує 10^9, 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