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

Парі з коробками

Парі з коробками

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

У Вас в компанії новий кур'єр, який може доставляти певну кількість товарі у різні місця. Йому необхідно доставити як мінімум X одиниць товару, в той час як вантажівка може взяти на борт не більше Y з них. Якщо завантажити більше Y, то під великою вагою вантажівка поломається. Якщо завантажити менше X, то це буде означати невиконанння завдання. У пункті завантаження є послідовність коробок, розміщена у ряд, які можна брати з собою. Певна коробка містить певну кількість одиниць товару.

Проте наш водій не ас. До того ж він доволі соромливий. Тому кур'єр вирішив вибрати довільним чином коробку, починаючи з якої він буде здійснювати завантаження. Потім він також навмання вибирає останню коробку яку візьме з собою (вона знаходиться між першою взятою і останньою у ряду включно). Всі коробки між вибраними двома (включно) завантажуються у автомобіль.

Ви і інші робітники почали заключати парі - чи поломається вантажівка, чи довезе кур'єр не весь необхідний товар чи все ж йому вдасться виконати завдання. Це спантеличило Вас. Чому рівна ймовірність кожної з вказаних подій? Вважайте, що розставити всі коробки у вантажівці кур'єр зможе (у всякому випадку, у нього є такий досвід).

Вхідні дані

Перший рядок містить кількість тестів T (0 < T100). Кожен тест складається з трьо рядків. Перший рядок містить кількість коробок N, другий рядок - послідовність з N (1 < N200000) символів (A-Z), B_1B_2...B_N (без пропусків, 'A' ≤ B_i ≤ 'Z'), які представляють кількості товарів у кожній коробці у тому ж порядку у якому вони розміщені на завантажувальному конвеєрі. Літерою A позначається пуста коробка, B - коробка з 1 единицею товару, і так далі до Z, яка позначає коробку з 25 одиницями товарів. У третьому рядку знаходиться два числа L і U (0LU50000). L - кількість одиниць товару, який слід доставити, U дорівнює максимальному можливому завантаженню вантажівки при якому автомобіль не поламається.

Ймовірність вибору початкової і кінцевої точки сегменту відбувається згідно рівномірному розподіленню. Довільна відповідь з точністю до 10^{-6} вважається вірною.

Вихідні дані

Для кожного тесту в окремому рядку вивести три дійсних числа. Перше число рівне ймовірності того що кур'єру вдасться перевезти весь товар, друге - що він не довезе весь товар, третє - що вантажівка поламається.

Приклад

Вхідні дані #1
2
4
KCHA
2 9
3
BCD
4 5
Вихідні дані #1
0.5 0.25 0.25
0.16666667 0.72222222 0.11111111