国王去世了，他的金子需要分给他的 $n$ 位妻子。由于他没有留下关于妻子们应得份额的遗嘱，她们开始争吵。第 $i$ 位妻子声称她应该得到 $a_i$ 第纳尔。

然而，国王的总财产只有 $s$ 第纳尔，且满足 $s \le a_1 + a_2 + \dots + a_n$。人们请来一位智者帮忙分配国王的遗产，但他表示自己只知道一种在两人之间公平分配金子的方法。

这种“公平分配”的方法如下：不失一般性，设两个人的要求分别为 $a_1 \le a_2$，且有 $b$ 第纳尔的金子需要分配，其中 $0 \le b \le a_1 + a_2$。如果 $b \le a_1$，则每个人各得到 $b/2$ 第纳尔。如果 $a_1 < b < a_2$，则第一个人得到 $a_1/2$ 第纳尔，第二个人得到 $b - a_1/2$ 第纳尔。最后，如果 $a_2 \le b$，则第一个人得到 $a_1/2 + (b - a_2)/2$，第二个人得到 $a_2/2 + (b - a_1)/2$。金子可以分割成任意分数，因此每个人得到的金额可以是小数。注意，每个人得到的金额是 $b$ 的单调连续函数。

现在，你被请来作为一位更睿智的人，帮助将金子分给 $n$ 位妻子。每位妻子得到的金子不应超过她所要求的数额。如果对于任意两位分别要求 $a_i$ 和 $a_j$ 第纳尔、最终分别得到 $c_i$ 和 $c_j$ 第纳尔的妻子，她们得到的份额 $c_i$ 和 $c_j$ 正好是分配 $c_i + c_j$ 第纳尔时的“公平分配”结果，那么这种分配就被称为公平的。

请帮助已故国王的妻子们分配遗产。

输入格式

第一行包含一个整数 $n$ —— 国王的妻子人数 ($2 \le n \le 5000$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$)。

第三行包含一个整数 $s$ ($0 \le s \le a_1 + a_2 + \dots + a_n$)。

输出格式

输出 $n$ 个浮点数 $c_1, c_2, \dots, c_n$ —— 在公平分配中每位妻子应得到的金子金额。

对于每一对妻子 $i$ 和 $j$，她们得到的份额与分配 $c_i + c_j$ 时的公平分配结果之间的绝对误差或相对误差不得超过 $10^{-9}$。所有 $c_i$ 的总和必须等于 $s$，且绝对误差或相对误差不超过 $10^{-9}$。

可以证明公平分配总是存在的。如果存在多种解，输出其中任意一个即可。

样例

样例输入 1

3
10 20 30
10

样例输出 1

3.33333333333333
3.33333333333333
3.33333333333333

样例输入 2

3
10 20 30
20

样例输出 2

5
7.5
7.5

样例输入 3

3
10 20 30
30

样例输出 3

5
10
15