Turn‐Based Circular Item Picking Game

There are \(n\) items numbered from \(0\) to \(n-1\) and each item \(i\) has a value \(v_i\). The value is defined by a repeating sequence: given an array \(w\) of length \(m\), we have \(v_i = w_{i \bmod m}\). Initially, all items are available. However, before the game begins the availability of some items may be toggled.

A and B play a multi‐round game as follows. At the beginning of each round, if there is no available item, the game immediately ends. Otherwise, player A must choose an available item with index \(i\) and take it. Then player B has the following option: he may choose either of the two items with indices \[ (i-d+n) \bmod n \quad \text{or} \quad (i+d) \bmod n \] provided that the chosen item is available, or he may skip his turn. (If both candidates are not available then B must skip.)

Both players play optimally to maximize the sum of the values of the items they take. In particular, each player will consider not only the current round’s gain but also the effect on future rounds. The final score for player B is defined as the total value of items taken by B when the game is played from the current state.

You are given \(q\) operations. Each operation provides an index \(x\) and toggles the availability of item \(x\): if it is available, it becomes unavailable, and if it is unavailable, it becomes available. After each operation, compute the final sum of values obtained by player B if the game were to start from the new state.

Note: Although \(n\) can be extremely large (up to \(10^{16}\)), the values \(v_i\) are generated via the short array \(w\) and the operations only toggle individual items. For the purpose of this problem, you may assume that the actual test cases involve a small \(n\) so that your program can simulate the game using, for example, bitmask dynamic programming.

inputFormat

The input is given as follows:

n d m
w[0] w[1] ... w[m-1]
q
x_1
x_2
... 
x_q

Here, \(n\) is the number of items, \(d\) is the offset used when calculating B's candidate indices, and \(w\) is an array of length \(m\) used to generate the item values \(v_i = w_{i \bmod m}\). Initially, all items (from \(0\) to \(n-1\)) are available. Then \(q\) operations follow; each operation is represented by an integer \(x\) (0-indexed) that toggles the availability of item \(x\).

outputFormat

For each of the \(q\) operations, output a line containing a single integer: the final sum of the values of the items taken by player B if the game starts from the current state.

sample

5 1 2
1 2
3
1
3
1

3