小 P 喜欢研究生活中各种各样的问题，最近他对洗澡这个问题颇有研究。小 P 所在的宿舍一层楼的澡堂有 $m$ 个洗澡的位置（即可以 $m$ 个人同时洗澡），每天有 $n$ 个人要洗澡，每个人前去洗澡的时间为 $t_i$，每个人洗澡的时间固定为 $T$。
第 $i$ 个人会在 $t_i$ 时刻去洗澡时，如果没有位置，他就只有等到有一个人洗完，他会在有一个人洗完后立刻去洗澡。
假设第 $i$ 个人最终开始洗澡的时间为 $s_i$，那么他会产生 $s_i-t_i$ 的不满度。
在接下来的 $q$ 天，在第 $j$ 天的时候，$x_j$ 会改变一下计划，洗澡的时间会修改为 $t'_j$。注意第 $j$ 天的修改不会持续到第 $j+1$ 天。
小 P 对不满度的和很有兴趣，所以他想请你对每一天求出所有人不满度的和。
输入格式
第一行四个正整数分别为 $n,m,q,T$，表示洗澡人数，澡堂个数，询问次数，以及洗澡的固定时间。
接下来的一行有 $n$ 个正整数，第 $i$ 个正整数 $t_i$ 表示第 $i$ 个人前去洗澡的时间，保证 $\forall i\in [1,n),t_i\le t_{i+1}$。
接下来的 $q$ 行，每行两个整数 $x_j,t'_j$，表示第 $x_j$ 个人的洗澡时间在这一天（且仅在这一天）变成了 $t'_j$。
输出格式
共 $q$ 行，第 $j$ 行一个整数表示第 $j$ 天的不满度之和。
样例输入 1
10 3 5 7 1 1 1 2 6 9 12 13 15 17 8 6 2 14 7 10 9 17 6 16
样例输出 1
24 15 21 18 18
样例输入 2
12 2 10 8 4 4 5 9 10 11 14 14 15 19 23 23 10 1 9 14 7 6 10 9 1 10 4 1 11 15 3 20 9 8 10 20
样例输出 2
137 138 145 147 137 127 145 122 144 136
数据范围
对于全部数据，$1\le m\le 5,1\le n\le 10^6,1\le q\le 10^5,1\le t_i,T\le 10^8$。
| 测试包编号 | $n\le$ | $m\le$ | $q\le$ | 特殊性质 | 分值 | 子任务依赖 |
|---|---|---|---|---|---|---|
| 1 | $10^3$ | $5$ | $10^3$ | 无 | 10 | 无 |
| 2 | $10^6$ | $1$ | $10^5$ | 无 | 20 | 无 |
| 3 | $10^6$ | $2$ | $10^5$ | 无 | 10 | 2 |
| 4 | $2\times 10^5$ | $5$ | $5\times 10^4$ | 无 | 20 | 1 |
| 5 | $10^6$ | $5$ | $10^5$ | $t_i$ 在 $[1,10^8]$ 中随机 | 20 | 无 |
| 6 | $10^6$ | $5$ | $10^5$ | 无 | 20 | 3, 4, 5 |
时空限制：512 MB，3s