食堂出新菜品了！为了让更多的同学来尝鲜，食堂决定推出代金券，每张价值 $1$ 元。可怜听说这个消息后，决定去食堂品尝一下新的菜品。代金券的消费规则如下：
- 可怜每消费 $c$ 元，便可以获得一张代金券。最后不满 $c$ 元的部分会抹去。
- 这些代金券可以在之后的任意一次用餐中使用，并且可以减少当次用餐实际付款 $1$ 元。注意利用代金券支出的部分不被记入可怜的花费。
- 如果可怜购买了价值 $a$ 元的菜品，她可以使用至多 $a$ 张消费券。
- 可怜只会使用自己通过消费已经得到的消费券，初始可怜没有消费券。
也就是说，如果可怜购买了共计 $a$ 元的菜品，并使用了 $b$ 张消费券，则她只需要付 $a-b$ 元钱，并会获得 $\lfloor \frac{a-b}{c} \rfloor$ 张消费券。
可怜打算按照顺序品尝食堂的 $n$ 套新菜品，第 $i$ 套菜品会花费 $a_i$ 元。可怜想要知道她最少需要花多少钱。
由于可怜是个精明的女孩子，她时常会更改自己的计划。可怜也想要知道在每一次更改计划后她最少需要花多少钱。
输入格式
第一行三个正整数 $n,Q,c$.
接下来一行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。
接下来 $Q$ 行，每行两个正整数 $x_i,y_i$，表示一次计划更改，Rikka 将第 $x_i$ 套菜品更改为一套花费 $y_i$ 元的菜品。
输出格式
第一行一个正整数，表示可怜在初始品尝计划中的最低花费。
接下来 $Q$ 行，第 $i$ 行一个正整数，表示在第 $i$ 次品尝计划更改后可怜的最低花费。
样例数据
样例 1 输入
5 5 4 23 38 19 37 14 1 12 2 17 3 41 4 33 5 18
样例 1 输出
106 96 80 97 94 97
样例 2 输入
5 5 3 9 8 7 6 5 1 19 2 18 3 17 4 16 5 15
样例 2 输出
27 34 42 49 57 64
子任务
Subtask $1$ ($5\%$): $1 \le n,Q \le 5,1 \le a_i,c,y \le 20$。
Subtask $2$ ($6\%$): $1 \le n,Q \le 20,1 \le a_i,c,y \le 100$。
Subtask $3$ ($12\%$): $1 \le n,Q \le 500,1 \le a_i,c,y \le 100000$。
Subtask $4$ ($17\%$): $1 \le n,Q \le 5000$。
Subtask $5$ ($11\%$): $c=1$。
Subtask $6$ ($15\%$): $c=2$。
Subtask $7$ ($11\%$): $a_i$ 在 $[1,r]$ 内均匀随机生成，其中 $1 \le r \le 10^{12}$。
Subtask $8$ ($23\%$): 无特殊限制。
对于所有测试数据，满足 $1 \le n,Q \le 3 \times 10^5,1 \le a_i,y \le 10^{12},1 \le c \le 10^9$。