eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Потрійний стрибок

Потрійний стрибок

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Потрійний стрибок відбувається наступним чином. Стрибун розганяється, добігає до певної позначки і робить три послідовні стрибки. Переможцем є той, чия сумарна довжина стрибків є найбільшою.

Ви приймаєте участь у змаганні і стрибаєте останнім. Усі Ваші суперники вже зробили стрибки, тому їх результати відомі.

Перший свій стрибок Ви вже зробили, його довжина дорівнює first. Довжина кожного з решти стрибків може з однаковою ймовірністю приймати будь-яке значення з відрізку [lower, upper], і не обов'язково бути цілим. Вам необхідно обчислити ймовірність того, що Ви займете i - те місце. Мцісце, яке Ви посіли, дорівнює одиниці плюс кількість суперників, що стрибнули далі за Вас.

Вхідні дані

Складається з декілької тестів. Перший рядок кожного тесту містить значення lower, upper, first (1 ≤lower≤ 1000, lowerupper1000, lowerfirstupper) та кількість Ваших суперників n (1 ≤n≤ 50). Другий рядок тесту містить n цілих чисел від 1 до 3000 - довжини потрійних стрибків усіх Ваших суперників.

Вихідні дані

Для кожного тесту в окремому рядку вивести n + 1 дійсне число - відповідно ймовірності того, що Ви посядете перше, друге, третє, ..., останнє місце. Усі ймовірності слід виводити з 4 десятковими знаками.

Приклад

Вхідні дані #1
1 2 1 4
1 2 3 4
1 10 5 8
1 2 3 5 10 11 12 19
Вихідні дані #1
0.5000 0.5000 0.0000 0.0000 0.0000
0.2222 0.6235 0.0556 0.0432 0.0556 0.0000 0.0000 0.0000 0.0000