RMQ
There is an array of N integers and M queries, each asking for the minimum value in a segment defined by endpoints l_i and r_i.
Input
The input consists of T test cases. Each test case is described by four integers: N, M, A, and B (1 ≤ N ≤ 25000, 1 ≤ A, B ≤ 10^9). Here, N is the size of the array, and M is the number of queries. The array and queries are generated as follows: create a sequence of numbers A·1 + B, A·2 + B, ..., A·(N + 2·M) + B, each taken modulo 2^32. The first N numbers of this sequence form the array. The numbers from N + 1 to N + 2·M, when taken modulo N, create M pairs of numbers l_i - 1 and r_i - 1, which represent the queries.
The input concludes with a line containing 0 0 0 0.
The total sum of N across all test cases does not exceed 10^9, and the total sum of M across all test cases does not exceed 20000000.
Output
For each test case, output the sum of the results of all queries on a separate line.
Explanation of the example
Array: 1574545889 2529925775 3485305661 145718251 1101098137 2056478023 3011857909 3967237795 627650385 1583030271
Queries:
8 4
4 10
6 2
8 8
4 10
6 6
2 8
4 10
10 6
2 8