거리 두기

코로나19 대유행은 많은 면에서 세상을 놀라게 했다. 거의 하룻밤 사이에 전 세계 사람들은 새로운 생활 방식에 적응해야 했고, 그 방식은 주로 지역 당국이 내린 예방 조치에 따라 형성되었다. 모든 조치의 목표는 질병의 확산을 억제하고 통제하는 것이었다.

더 파괴적인 유행이 먼 미래에 일어날 가능성은 낮지만, 그 상황에 대비하기 위해 크로아티아 국립 공중보건연구소는 여러 연구 부서를 열었다. 이 부서들의 주된 목표는 일반 대중이 새로운 예방 조치를 빠르게 따를 수 있도록 매우 효율적인 프로토콜을 개발하는 것이다.

Alenka는 그중 한 부서에서 일한다. 그녀는 사람들이 한 줄로 서 있는 상황을 조사한다. 예를 들어 우체국 앞에 줄을 선 경우다. 여기에 새로운 안전 수칙이 시행되어, 임의의 두 사람 사이의 거리가 최소 $D$ 이상이어야 한다고 정해졌다.

Alenka는 앱도 만들었다. 사용자는 거리 $D$와 선 위에 있는 $N$명의 위치 좌표를 입력한다. 앱은 선을 그리고, 집단이 수칙을 만족하는 배치에 도달하는 데 걸리는 최소 시간 $t_{opt}$(초)를 계산한다. 앱은 사람들이 즉시 최적으로 재배치를 시작하며, 모든 사람이 초당 1 단위의 같은 일정한 속력으로 움직인다고 가정한다.

이제 그녀는 사용자가 선을 탭하여 위치를 찍는 방식으로 $M$명을 추가할 수 있는 기능을 넣으려 한다. 앱은 탭할 때마다, 즉 새로운 사람이 집단에 추가될 때마다 $t_{opt}$를 다시 계산해야 한다.

Alenka가 이 기능을 구현하도록 도와라.

첫 번째 줄에 세 정수 $N$, $M$, $D$가 주어진다.

두 번째 줄에는 처음 있던 $N$명의 위치 $a_1, \dots, a_N$이 주어진다.

세 번째 줄에는 추가되는 $M$명의 위치 $b_1, \dots, b_M$이 주어진다.

한 줄에 $M$개의 수를 출력한다. $i$번째 수는 집단이 $a_1, a_2, \dots, a_N, b_1, \dots, b_i$ 위치에 있는 $(N + i)$명일 때의 $t_{opt}$ 값이다.

각 수는 소수점 뒤에 불필요한 0이 없는 10진수 표기로 출력한다. 예를 들어 1.2300 대신 1.23을, 123.이나 123.0 대신 123을 출력한다. 모든 답은 유한한 소수 표현을 가짐을 증명할 수 있다.

모든 서브태스크에서 $1 \le D, a_1, \dots, a_N, b_1, \dots, b_M \le 10^9$이다.