COVID-19 疫情以多种方式让世界措手不及。几乎在一夜之间，全球各地的人们不得不适应一种新的生活方式，这主要归功于当地政府发布的预防措施，其目的都是为了抑制和控制疾病的传播。

为了更好地应对未来可能发生的更具破坏性的疫情，克罗地亚国家公共卫生研究所决定开设多个研究部门。这些部门的主要目标是制定高效的协议，帮助广大民众快速遵守新的预防措施。

Alenka 在其中一个部门工作，她目前正在研究这样一种场景：一群人排成一列（例如在邮局前），突然实施了一项新的安全措施，要求任意两人之间的距离至少为 $D$。

她还开发了一个应用程序，允许用户指定距离 $D$ 和直线上 $N$ 个人的位置坐标。该应用程序随后会绘制一条代表该情况的直线，并计算这群人达到满足预防措施的新排列所需的最短时间（以秒为单位），记为 $t_{\text{opt}}$。该应用程序假设人们会立即开始以最优方式重新排列，并且所有人均以每秒一个单位的恒定速度移动。

她现在想增加一项新功能，使用户能够通过在绘制的直线上点击来向群体中添加 $M$ 个人，从而指定他们的位置。该应用程序需要在每次点击后重新计算 $t_{\text{opt}}$，即在向群体中添加每个人之后。

你的任务是通过实现此功能来帮助 Alenka。

输入格式

第一行包含题目描述中的整数 $N$、$M$ 和 $D$。

第二行包含 $N$ 个整数 $a_1, \dots, a_N$，即初始 $N$ 个人的位置。

第三行包含 $M$ 个整数 $b_1, \dots, b_M$，即额外 $M$ 个人的位置。

输出格式

在一行中输出 $M$ 个数字，其中第 $i$ 个数字表示当群体由位于 $a_1, a_2, \dots, a_N, b_1, \dots, b_i$ 的 $(N + i)$ 个人组成时，$t_{\text{opt}}$ 的值。

以不带末尾零的十进制表示法输出每个数字，例如输出 $1.23$ 而不是 $1.2300$，输出 $123$ 而不是 $123.$ 或 $123.0$。可以证明答案总是具有有限的十进制表示。

数据范围

在所有子任务中，均满足 $1 \le D, a_1, \dots, a_N, b_1, \dots, b_M \le 10^9$。

样例

输入格式 1

2 1 2
1 3
2

输出格式 1

1

输入格式 2

0 5 3
1 2 3 4 5

输出格式 2

0 1 2 3 4

说明

第二个样例的说明：

输入格式 3

3 3 3
3 3 3
3 3 3

输出格式 3

4.5 6 7.5