Measures

The COVID-19 pandemic took the world by surprise in many ways. Almost overnight, people around the globe had to adapt to a new way of life, shaped mainly by the preventive measures issued by local authorities. Every measure aimed to suppress and control the spread of the disease.

To prepare for the unlikely event of a more devastating outbreak in the future, the Croatian National Institute of Public Health opened several research departments. The main goal of these departments is to develop highly efficient protocols that help the general population adhere quickly to a new preventive measure.

Alenka works in one of these departments. She studies a situation in which a group of people stands in a line, for example in front of a post office, and a new safety measure requires that the distance between any two people is at least $D$.

Alenka also built an app. The user enters a distance $D$ and the locations of $N$ people as coordinates on a line. The app draws the line and calculates the smallest time $t_{opt}$, in seconds, that the group needs to reach an arrangement that satisfies the measure. The app assumes that people start rearranging optimally at once, and that everyone moves at the same constant speed of one unit per second.

Now she wants to add a feature that lets the user add $M$ more people by tapping on the line at their locations. The app must recalculate $t_{opt}$ after each tap, that is, after each new person is added to the group.

Help Alenka implement this feature.

The first line contains three integers $N$, $M$, and $D$.

The second line contains $N$ integers $a_1, \dots, a_N$, the locations of the initial people.

The third line contains $M$ integers $b_1, \dots, b_M$, the locations of the additional people.

Output $M$ numbers on one line. The $i$-th number is the value of $t_{opt}$ when the group consists of the $(N + i)$ people at locations $a_1, a_2, \dots, a_N, b_1, \dots, b_i$.

Print each number in decimal notation without trailing zeroes. For example, print 1.23 instead of 1.2300, and 123 instead of 123. or 123.0. It can be proven that every answer has a finite decimal representation.

In all subtasks, $1 \le D, a_1, \dots, a_N, b_1, \dots, b_M \le 10^9$.