Easily limited memory

Time limit7sMemory limit4 MB

Summary

Find the q-th smallest elements of a pseudorandom sequence without storing the whole sequence, then print the sum of the answers.

Level: Medium7 of 10
Topics: Binary search, Sorting, Divide and conquer, Math
Solved: No attempts yet

Problem

There is an array X of N integers. Several queries follow, and each query is a single integer q. For each query, find the q-th smallest element of X. Here q is a 0-based index, so q = 0 asks for the smallest element and q = 1 asks for the second smallest.

The task looks easy, because sorting X and then reading off the answers would be enough. To block that approach, the memory limit here is very small. You cannot store all of X. The number of queries is small, so you can store all of the query data.

X is not given directly. It is generated from N, x0, a, and b by the following pseudocode.

X[0] = x0
for i = 1 to N-1:
    X[i] = (X[i-1] * a + b) % 1000000007

Watch out for integer overflow in the multiplication.

Write a program that prints the sum of the answers to all queries.

Input

The first line contains four integers N, x0, a, and b separated by spaces. (1 ≤ N ≤ 1,000,000, 0 ≤ x0, a, b ≤ 1,000,000,006)

The second line contains the number of queries Q. (1 ≤ Q ≤ 100)

The third line contains Q integers separated by spaces, one per query. (0 ≤ q ≤ N-1)

Output

Print one integer, the sum of the answers to all queries.

Examples8

Example 1
Input
```
5 100 1 5
2
0 3
```
Expected output
```
215
```
Example 2
Input
```
1 0 0 0
1
0
```
Expected output
```
0
```

Example 3

Input

1 1000000006 999999999 1000000006
1
0

Expected output

1000000006

Example 4
Input
```
6 7 0 0
6
0 1 2 3 4 5
```
Expected output
```
7
```
Example 5
Input
```
10 42 1 0
5
0 9 4 4 9
```
Expected output
```
210
```

Example 6

Input

20 1000000000 1 1
20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Expected output

7000000099

Example 7
Input
```
50 0 0 32767
3
0 1 49
```
Expected output
```
65534
```

Example 8

Input

10 32767 1 1
10
0 1 2 3 4 5 6 7 8 9

Expected output