Пари с коробками
У Вас в компании новый курьер, который может доставлять определенное количество товаров в разные места. Ему необходимо доставить как минимум 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} считается верным.
Выходные данные
Для каждого теста в отдельной строке вывести три действительных числа. Первое число равно вероятности того что курьеру удастся перевезти весь товар, второе - что он не довезет весь товар, третье - что грузовик сломается.