题目描述

小 D 是一家建筑公司的老板。

他需要完成一个建筑任务，任务被描述为 $n$ 个整数 $x_1\sim x_n$ 以及一个参数 $m$。

现在他需要执行如下操作：

1. 现在有 $m$ 个未建造的建筑，高度都是 0。
2. 对于 $1\le i\le n$，依次执行：将编号在 $1\sim x_i$ 的建筑高度都减少 1，将编号在 $x_i+1\sim m$ 的建筑高度都增加 1。如果有建筑高度为负数，则将它的高度变成 0。

小 D 能够获得的收益就是最后所有建筑的高度之和。

小 D 本以为问题就到此结束了，结果没想到委托方经常临时变卦，即将任务中的某个 $x$ 修改为 $c$。为了确保建筑任务的顺利执行，你，作为小 D 的秘书，需要在每次修改之后将预期收益告诉小 D。

输入格式

第一行四个整数 $C,n,m,q$。$C$ 是测试点编号，在样例中 $C=0$；$n$ 是任务描述序列的长度；$m$ 是参数；$q$ 是委托方修改序列的次数。

第二行 $n$ 个整数表示 $x_i$。

接下来 $q$ 行，每行两个整数 $i,c$，表示将 $x_i$ 修改为 $c$。注意，修改是永久的。

输出格式

一共输出 $q$ 行，每行表示修改后小 D 能够获得的收益。

样例 1

输入

0 3 4 2
1 2 3
1 4
3 0

输出

2
6

样例 1 解释

第一次修改后的 $x=\{4,2,3\}$，执行完操作后 $m$ 个建筑的高度分别为 $0,0,0,2$，总和为 2。

数据范围

对于 100% 的数据，满足 $1\le n,m\le 10^5$，$0\le x_i\le m$，$1\le i\le n$，$0\le c\le m$。

• 特殊性质 A：保证 $n\le 3$。
• 特殊性质 B：保证 $m\le 3$。