Background

CTT2021 D4T3

Problem Description

There are $n$ items, numbered $0, \cdots, n-1$. The value of item $i$ is defined as $v_i$.

A and B take turns playing a game, which consists of multiple rounds.

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

Suppose the item A takes has index $i$. Next, B may choose one untaken item from item $(i - d + n) \bmod n$ and item $(i + d) \bmod n$ to take, or B may choose to skip this action. Then the game proceeds to the next round. In particular, if both of these items have already been taken, B can only choose to skip.

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

In addition, before the game starts, some items may be unavailable. During the game, unavailable items are ignored, i.e., neither A nor B can take unavailable items. When all available items have been taken, the game ends immediately.

Initially, all items are available. Your program needs to support $q$ operations. In each operation, given 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 values of the items taken by B when the game ends.

Unfortunately, this is an IO problem: the number of items may be up to $10^{16}$. As an OIer, you cannot handle data at such a large scale, so $v_i$ will be generated in a special way: given an array $w$ of length $m$, $v_i = w_{i \bmod m}$.

Input Format

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

The second line contains $m$ integers. 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 Format

Output $q$ lines, each containing one integer, corresponding to the answer after each operation.

5 2 3 2
1 3 2
1
1

3
4

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

581
460
420
541
702

Hint

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 constraints.

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

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

Translated by ChatGPT 5