P9000 [CEOI 2022] Measures

There are $N$ people standing on a number line. Their initial positions are $a_1,a_2,\ldots,a_N$, and they can move at a speed of $1$ unit length per second. For well-known reasons, they need to keep social distance, meaning that the distance between any two people must be at least $D$. Alenka designed an app to quickly compute the minimum time needed for these $N$ people to achieve social distancing by moving. Now she wants to add a new feature: support dynamically adding a person at position $b_i$. You need to implement a program to complete this feature.

The first line contains three integers $N,M,D$. The next line contains $N$ integers $a_1,\ldots,a_N$, representing the initial $N$ people. The next line contains $M$ integers $b_1,\ldots,b_M$, representing the $M$ people added one by one in order.

Output one line with $M$ numbers. The $i$-th number represents the minimum time required after adding the $i$-th person. You must output the exact value of this time, without extra trailing $0$.

### Explanation for Sample 2  ### Constraints For all testdata, $1\le D,a_1,\ldots,a_N,b_1,\ldots,b_M\le 10^9$. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $0\le N\le 2000$，$1\le M\le 10$ | $10$ | | $2$ | $0\le N\le 2\times 10^5$，$1\le M\le 10$ | $14$ | | $3$ | $N=0$，$1\le M\le 2\times 10^5$，$b_1\le \cdots\le b_M$ | $35$ | | $4$ | $N=0$，$1\le M\le 2\times 10^5$ | $41$ | Translated by ChatGPT 5