RMQ — Eolymp

Input

The input consists of $T$ test cases. Each test case includes four integers: $N$ , $M$ , $A$ , and $B$ ( $1 \leq N \leq 25000$ 1 \le N \le 25000, $1 \leq A, B \leq 1 0^{9}$ 1 \le A, B \le 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:

Write the sequence of numbers $A \cdot 1 + B, A \cdot 2 + B, \dots, A \cdot (N + 2 \cdot M) + B$ A \cdot 1 + B,\; A \cdot 2 + B,\; \ldots,\; A \cdot (N + 2 \cdot M) + B modulo $2^{32}$ 2^{32}. The first $N$ numbers in this sequence form the elements of the array. The numbers from $N + 1$ N + 1 to $N + 2 \cdot M$ N + 2 \cdot M, taken modulo $N$ , form $M$ pairs of numbers $l_{i} - 1$ l_i - 1 and $r_{i} - 1$ r_i - 1, which are used as the query endpoints.

The input ends with a line containing $0000$ .

The sum of $N$ over all test cases does not exceed $1 0^{9}$ 10^9, and the sum of $M$ over all test cases does not exceed $20000000$ .

Output

For each test case, print the sum of the results of all queries on a separate line.

Examples

Example 1

Loading

Note

Array: $15745458892529925775348530566114571825111010981372056478023301185790939672377956276503851583030271$ 1574545889\ 2529925775\ 3485305661\ 145718251\ 1101098137\ 2056478023\ 3011857909\ 3967237795\ 627650385\ 1583030271

Queries:

$84$

$410$

$62$

$88$

$410$

$66$

$28$

$410$

$106$

$28$