Little P likes to study various problems in life, and recently he has been studying the problem of taking a shower. In the dormitory where Little P lives, there are $m$ shower stalls on one floor (meaning $m$ people can shower at the same time). Every day, $n$ people need to shower. The time each person arrives to shower is $t_i$, and the duration of each shower is fixed at $T$.
When the $i$-th person arrives at time $t_i$ to shower, if there is no stall available, they must wait until someone finishes, at which point they will immediately start showering.
Suppose the time the $i$-th person actually starts showering is $s_i$. Then they incur a dissatisfaction level of $s_i - t_i$.
Over the next $q$ days, on the $j$-th day, the plan for person $x_j$ changes, and their arrival time becomes $t'_j$. Note that the change on the $j$-th day does not persist to the $(j+1)$-th day.
Little P is interested in the sum of dissatisfaction levels, so he wants you to calculate the sum of everyone's dissatisfaction levels for each day.
Input
The first line contains four positive integers $n, m, q, T$, representing the number of people, the number of shower stalls, the number of queries, and the fixed shower duration, respectively.
The next line contains $n$ positive integers, where the $i$-th positive integer $t_i$ represents the time the $i$-th person arrives to shower. It is guaranteed that $\forall i \in [1, n), t_i \le t_{i+1}$.
The next $q$ lines each contain two integers $x_j, t'_j$, representing that the arrival time of the $x_j$-th person changes to $t'_j$ on that day (and only on that day).
Output
There are $q$ lines, where the $j$-th line contains an integer representing the sum of dissatisfaction levels on the $j$-th day.
Examples
Input 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
Output 1
24 15 21 18 18
Input 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
Output 2
137 138 145 147 137 127 145 122 144 136
Constraints
For all data, $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$.
| Test Case ID | $n \le$ | $m \le$ | $q \le$ | Special Property | Score | Subtask Dependency |
|---|---|---|---|---|---|---|
| 1 | $10^3$ | $5$ | $10^3$ | None | 10 | None |
| 2 | $10^6$ | $1$ | $10^5$ | None | 20 | None |
| 3 | $10^6$ | $2$ | $10^5$ | None | 10 | 2 |
| 4 | $2 \times 10^5$ | $5$ | $5 \times 10^4$ | None | 20 | 1 |
| 5 | $10^6$ | $5$ | $10^5$ | $t_i$ is random in $[1, 10^8]$ | 20 | None |
| 6 | $10^6$ | $5$ | $10^5$ | None | 20 | 3, 4, 5 |