반쪽은 같지 않다

왕이 죽어 그의 금을 n명의 왕비에게 나눠야 한다. 왕은 왕비들에게 각각 얼마씩 줄지 유언을 남기지 않았고, 그래서 왕비들은 다투기 시작했다. i번째 왕비는 자신이 ai디나르를 받아야 한다고 주장했다. 그런데 왕의 재산은 겨우 s디나르밖에 되지 않았고, s ≤ a1 + a2 + . . . + an이다. 왕의 유산을 나누는 일을 돕기 위해 현자가 불려 왔다. 그러나 그는 두 사람 사이에서 금을 공정하게 나누는 방법밖에 모른다고 말했다.

그 공정한 방법은 다음과 같다. 일반성을 잃지 않고 두 사람의 주장이 a1 ≤ a2이고, 나눌 금이 b디나르이며 0 ≤ b ≤ a1 + a2라고 하자. b ≤ a1이면 두 사람은 각각 b/2디나르를 받는다. a1 < b < a2이면 첫 번째 사람은 a1/2디나르를, 두 번째 사람은 b − a1/2디나르를 받는다. 마지막으로 a2 ≤ b이면 첫 번째 사람은 a1/2+ (b−a2)/2를, 두 번째 사람은 a2/2+ (b−a1)/2를 받는다. 금은 얼마든지 잘게 나눌 수 있으므로 받는 양은 분수가 될 수 있다. 두 사람이 받는 양은 b에 대한 단조 증가 연속 함수이다.

이제 더 현명한 사람인 당신이 왕비 n명에게 금을 나눠 주어야 한다. 각 왕비는 자신이 주장한 양보다 많이 받아서는 안 된다. 어떤 두 왕비가 각각 ai디나르와 aj디나르를 주장하고 각각 ci디나르와 cj디나르를 받았을 때, 이 값들이 두 사람 사이에서 ci + cj디나르를 나누는 공정한 방법이 된다면 그 분배를 공정하다고 한다.

죽은 왕의 왕비들이 유산을 나누도록 도와라.

첫 번째 줄에는 왕비의 수 n이 주어진다. (2 ≤ n ≤ 5000)

두 번째 줄에는 n개의 정수 a1, a2, . . . , an이 주어진다. (1 ≤ ai ≤ 5000)

세 번째 줄에는 정수 s가 주어진다. (0 ≤ s ≤ a1 + a2 + . . . + an)

공정한 분배에서 각 왕비가 받아야 할 금의 양 c1, c2, . . . , cn을 실수 n개로 출력한다. 모든 왕비 쌍 i, j에 대해, 두 왕비가 받은 양과 ci + cj를 두 사람 사이에서 공정하게 나눌 때의 양 사이의 절대 오차 또는 상대 오차가 10−9을 넘지 않아야 한다. ci의 합은 s와 같아야 하며, 절대 오차 또는 상대 오차가 10−9 이하여야 한다.

공정한 분배는 항상 존재함을 증명할 수 있다. 답이 여러 개라면 아무거나 출력한다.