Problem Description

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.

Input Format

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 Format

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$.

2 1 2
1 3
2

1

0 5 3

1 2 3 4 5

0 1 2 3 4

3 3 3
3 3 3
3 3 3

4.5 6 7.5

Hint

Explanation for Sample 2

Constraints

For all testdata, $1\le D,a_1,\ldots,a_N,b_1,\ldots,b_M\le 10^9$.

Translated by ChatGPT 5