There are $n$ items, numbered $0, \dots, n-1$, where the value of item $i$ is $v_i$.

A and B are playing a game that consists of multiple rounds.

At the beginning of each round, if all available items have been taken, the game ends immediately. Otherwise, A must choose an available item and take it.

Suppose A chooses item $i$. Next, B can choose to take an available item from either $(i - d + n) \bmod n$ or $(i + d) \bmod n$, or B can choose to skip their turn. The game then proceeds to the next round. Specifically, if both of these items have already been taken, B must skip their turn.

Both A and B want to maximize the sum of the values of the items they take. Assume both A and B play optimally.

Additionally, before the game starts, some items may be unavailable. During the game, unavailable items are ignored: neither A nor B can take an unavailable item, and the game ends immediately when all available items have been taken.

Initially, all items are available. Your program needs to support $q$ operations. Each operation provides an $x$: if item $x$ is unavailable, it becomes available; if it is available, it becomes unavailable. After each operation, you need to answer: assuming the game starts from the current state, what is the sum of the values of the items taken by B when the game ends?

Unfortunately, this is an IO problem, and the number of items can be as large as $10^{16}$. As an OIer, you cannot handle such large data, so $v_i$ is generated using a special method: given an array $w$ of length $m$, $v_i = w_{i \bmod m}$.

Input

The first line contains four positive integers $n, d, m, q$, where $1 < n \le 10^{16}$, $1 \le d < n$, $1 \le m \le 2 \times 10^4$, and $q \le 10^5$.

The second line contains $m$ integers, where the $i$-th integer represents the value of $w_{i-1}$, with $1 \le w_i \le 400$.

The next $q$ lines each contain an integer $x$, representing an operation on item $x$. It is guaranteed that $0 \le x < n$.

Output

Output $q$ lines, each containing an integer representing the answer after each operation.

Examples

Input 1

5 2 3 2
1 3 2
1
1

Output 1

3
4

Note 1

In this example, $v_0 = 1, v_1 = 3, v_2 = 2, v_3 = 1, v_4 = 3$.

After the first operation, item $1$ is unavailable. Both sides play optimally, and the sum of the values of the items taken by B is $3$.

After the second operation, all items are available. Both sides play optimally, and the sum of the values of the items taken by B is $4$.

Input 2

10 4 5 5
40 355 190 215 161
3
4
0
3
4

Output 2

581
460
420
541
702

Input 3

See the provided files.

Constraints

Subtask 1 (5 pts): $n \le 20, q = 1$

Subtask 2 (10 pts): $n \le 10^5, q = 1$

Subtask 3 (15 pts): $n, q \le 10^5$

Subtask 4 (30 pts): $q = 1$

Subtask 5 (40 pts): No special restrictions.

If necessary, you can use __int128 to handle long long multiplication modulo $m$. Below is an example of using __int128 to calculate $a \times b \bmod m$:

long long a = 1e15;
long long b = 1e15;
long long m = 12345678910;
long long c = ((__int128) a * b) % m;