Problem Description

There are $N$ people standing on a number line, with their initial positions being $a_1, a_2, \ldots, a_N$. They can move at a speed of 1 unit length per second.

Due to well-known reasons, they need to maintain social distancing, which means the distance between any two people must be at least $D$.

Alenka has designed an app to quickly calculate the minimum time required for these $N$ people to move and maintain social distancing. Now, she wants to add a new feature: supporting the dynamic addition of a person at position $b_i$.

You need to implement a program to accomplish 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 positions of the $N$ people.

The next line contains $M$ integers $b_1, \ldots, b_M$, representing the positions of the $M$ people to be added sequentially.

Output Format

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

Sample Input and Output

Sample Input #1

2 1 2
1 3
2

Sample Output #1

1

Sample Input #2

0 5 3

1 2 3 4 5

Sample Output #2

0 1 2 3 4

Sample Input #3

3 3 3
3 3 3
3 3 3

Sample Output #3

4.5 6 7.5

Notes

Explanation of Sample 3

Data Size and Constraints

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

见题面 Input 部分

见题面 Output 部分