题目描述

有 $n$ 件物品，用 $0, \cdots, n-1$ 对它们编号，规定物品 $i$ 的价值为 $v_i$。

$A$ 和 $B$ 正在轮流玩一个游戏，该游戏会进行多轮。

每轮开始时，如果所有可用的物品都已经被取走，游戏将立刻结束。否则，$A$ 必须选择一件未被取走的物品，将其取走。

假设 $A$ 取走的物品编号为 $i$。接下来，$B$ 可以选择从物品 $(i - d + n) \bmod n$ 和物品 $(i + d) \bmod n$ 中选取一件未被取走的物品，将其取走；或者他可以选择跳过本次操作。随后游戏进入到下一轮。特别地，如果这两件物品都已经被取走了，$B$ 只能选择跳过本次操作。

$A$ 和 $B$ 都想最大化自己取走的物品的价值之和，我们假定 $A$ 与 $B$ 都采取了最优策略。

此外，在游戏开始前，有一些物品可能是不可用的。在游戏过程中，不可用的物品将会被忽略，即：$A$ 和 $B$ 都不能取走不可用的物品；当所有可用的物品都已经被取走时，游戏立刻结束。

初始时，所有物品都是可用的。你的程序需要支持 $q$ 次操作，每次操作的内容为：给定一个 $x$，如果物品 $x$ 是不可用的，它将变为可用的；如果它是可用的，它将变为不可用的。每次操作后，你需要回答：假设从当前状态开始游戏，游戏结束时 $B$ 取走的物品的价值之和。

不幸的是，这是一道 IO 题，物品的数量可能会达到 $10^{16}$。身为一个 OIer，你无法处理如此大规模的数据，因此 $v_i$ 将会用一种特殊的方法生成：给定一个长度为 $m$ 的数组 $w$，$v_i = w_{i \bmod m}$。

---

输入格式

输入的第一行包含四个正整数 $n, d, m, q$，保证 $1 < n \le 10^{16}$, $1\le d < n$, $1 \le m \le 2\times 10^4$, $q \le 10^5$。

输入的第二行包含 $m$ 个整数，第 $i$ 个整数表示 $w_{i-1}$ 的值，保证 $1 \le w_i \le 400$。

接下来的 $q$ 行，每行包含一个整数 $x$，表示一次对物品 $x$ 的操作。保证 $0 \le x < n$。

---

输出格式

输出 $q$ 行，每行一个整数，对应一次操作之后的答案。

---

样例 1

输入

5 2 3 2
1 3 2
1
1

输出

3
4

在这组样例中，$v_0 = 1$, $v_1 = 3$, $v_2 = 2$, $v_3 = 1$, $v_4 = 3$。

在第一次操作后，物品 $1$ 处于不可用状态。双方都采取最优策略进行游戏，最终 $B$ 取走的物品价值之和为 $3$。

在第二次操作后，所有物品都处于可用状态。双方都采取最优策略进行游戏，最终 $B$ 取走的物品价值之和为 $4$。

---

样例 2

输入

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

输出

581
460
420
541
702

---

样例 3

见附加文件中的 3.in 与 3.ans。

---

数据范围与提示

Subtask 1 ($5$ 分) : $n \le 20$, $q = 1$
Subtask 2 ($10$ 分) : $n \le 10^5$, $q = 1$
Subtask 3 ($15$ 分) : $n, q \le 10^5$
Subtask 4 ($30$ 分) : $q = 1$
Subtask 5 ($40$ 分) : 无特殊限制。

如有需要，可以使用 __int128 处理 long long 乘法取模，下面是一个使用 __int128 计算 $a \times b \bmod m$ 的例子：

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