Парі з коробками
У Вас в компанії новий кур'єр, який може доставляти певну кількість товарі у різні місця. Йому необхідно доставити як мінімум X одиниць товару, в той час як вантажівка може взяти на борт не більше Y з них. Якщо завантажити більше Y, то під великою вагою вантажівка поломається. Якщо завантажити менше X, то це буде означати невиконанння завдання. У пункті завантаження є послідовність коробок, розміщена у ряд, які можна брати з собою. Певна коробка містить певну кількість одиниць товару.
Проте наш водій не ас. До того ж він доволі соромливий. Тому кур'єр вирішив вибрати довільним чином коробку, починаючи з якої він буде здійснювати завантаження. Потім він також навмання вибирає останню коробку яку візьме з собою (вона знаходиться між першою взятою і останньою у ряду включно). Всі коробки між вибраними двома (включно) завантажуються у автомобіль.
Ви і інші робітники почали заключати парі - чи поломається вантажівка, чи довезе кур'єр не весь необхідний товар чи все ж йому вдасться виконати завдання. Це спантеличило Вас. Чому рівна ймовірність кожної з вказаних подій? Вважайте, що розставити всі коробки у вантажівці кур'єр зможе (у всякому випадку, у нього є такий досвід).
Вхідні дані
Перший рядок містить кількість тестів T (0 < T ≤ 100). Кожен тест складається з трьо рядків. Перший рядок містить кількість коробок N, другий рядок - послідовність з N (1 < N ≤ 200000) символів (A-Z), B_1B_2...B_N (без пропусків, 'A' ≤ B_i ≤ 'Z'), які представляють кількості товарів у кожній коробці у тому ж порядку у якому вони розміщені на завантажувальному конвеєрі. Літерою A позначається пуста коробка, B - коробка з 1 единицею товару, і так далі до Z, яка позначає коробку з 25 одиницями товарів. У третьому рядку знаходиться два числа L і U (0 ≤ L ≤ U ≤ 50000). L - кількість одиниць товару, який слід доставити, U дорівнює максимальному можливому завантаженню вантажівки при якому автомобіль не поламається.
Ймовірність вибору початкової і кінцевої точки сегменту відбувається згідно рівномірному розподіленню. Довільна відповідь з точністю до 10^{-6} вважається вірною.
Вихідні дані
Для кожного тесту в окремому рядку вивести три дійсних числа. Перше число рівне ймовірності того що кур'єру вдасться перевезти весь товар, друге - що він не довезе весь товар, третє - що вантажівка поламається.