상자 내기

회사에 새로 들어온 배달 기사가 트럭에 물건을 싣고 배달을 나간다. 배달해야 하는 물건은 최소 $L$개이고, 트럭이 견딜 수 있는 물건은 최대 $U$개다. $U$개보다 많이 실으면 무게 때문에 트럭이 고장 나고, $L$개보다 적게 실으면 임무를 마치지 못한다.

적재장에는 상자 $N$개가 한 줄로 놓여 있고, 상자마다 물건이 정해진 개수만큼 들어 있다. 기사는 도와달라는 말을 꺼내기 부끄러워서, 줄에 놓인 상자 중 시작 상자 하나를 완전히 무작위로 고른다. 그다음 시작 상자부터 줄의 끝까지 놓인 상자 중에서 끝 상자 하나를 다시 무작위로 고른다. 시작 상자와 끝 상자를 포함해 그 사이에 있는 상자를 모두 트럭에 싣는다.

동료들은 트럭이 고장 날지, 물건을 너무 적게 실을지, 아니면 운 좋게 임무를 제대로 마칠지를 두고 내기를 시작했다. 세 결과가 나올 확률을 각각 구하라. 기사가 고른 상자는 언제나 트럭 적재함에 모두 들어간다고 가정한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에 상자의 개수 $N$이 주어진다. 둘째 줄에 공백 없이 대문자 $N$개로 이루어진 문자열 $B_1 B_2 \dots B_N$이 주어지며, 적재장에 놓인 순서대로 각 상자에 든 물건의 개수를 나타낸다. A는 빈 상자, B는 물건이 1개 든 상자를 뜻하고, 같은 방식으로 Z는 물건이 25개 든 상자를 뜻한다. 셋째 줄에 두 정수 $L$과 $U$가 주어진다. $L$은 기사가 배달해야 하는 물건의 개수이고, $U$는 트럭이 고장 나지 않고 실을 수 있는 물건의 최대 개수다.

• $0 < T \le 100$
• $1 < N \le 200000$
• $B_i$는 A부터 Z까지의 대문자
• $0 \le L \le U \le 50000$
• 시작 상자는 상자 $N$개 중에서 균등한 확률로 고르고, 끝 상자는 시작 상자부터 마지막 상자까지 중에서 균등한 확률로 고른다.

각 테스트 케이스마다 한 줄에 실수 세 개를 공백 하나로 구분해 출력한다. 첫 번째 수는 기사가 임무를 제대로 마칠 확률, 두 번째 수는 물건을 너무 적게 실을 확률, 세 번째 수는 트럭이 고장 날 확률이다. 세 값 모두 소수점 아래 여섯째 자리까지 반올림해 출력한다.