eolymp
bolt
Try our new interface for solving problems

RMQ

Time limit 2 seconds
Memory limit 256 MiB

Задан массив из n целых чисел и m запросов вида: найти минимум на отрезке с концами l_i, r_i.

Input data

Состоит из 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.

Output data

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

Examples

Input example #1
10 10 955379886 619166003
0 0 0 0
Output example #1
7671393960

Note

Массив: 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

Author S.Kopeliovich, S.Rogulenko