Box Betting#1197
There is a new courier in your company who can deliver a certain number of items to various locations. He must deliver at least items, but the truck can carry at most items. If more than items are loaded, the truck will break down from the weight. If fewer than items are loaded, it means the assignment is not fulfilled. At the loading dock, there is a row of boxes, and each box contains a certain number of items.
However, the driver is not a professional and is also quite shy. Therefore, he decides to randomly select the box where loading begins. Then, he randomly selects the ending box (between the chosen start and the last box in the row, inclusive). All boxes between these two selected boxes (inclusive) are loaded onto the truck.
You and your coworkers start betting — will the truck break down, will the courier fail to deliver enough items, or will he successfully fulfill the assignment? What is the probability of each event? Assume the courier can always fit all the selected boxes in the truck.
The first line contains the number of test cases (0 < T \leq 100). Each test consists of three lines. The first line contains the number of boxes . The second line contains a sequence of (1 < N \leq 200000) characters B_1B_2 \dots B_N (no spaces, \text{A} \leq B_i \leq \text{Z}), where each character represents the number of items in a box in the order they are arranged on the conveyor belt. Letter denotes an empty box, denotes a box with item, up to which denotes a box with items. The third line contains two numbers and (0 \leq L \leq U \leq 50000). is the required item count for delivery, and is the truck's maximum load without breaking.
Both the starting and ending points for the segment are chosen uniformly at random. Any answer within 10^{-6} of the correct value will be accepted.
For each test case, output three real numbers in a separate line: the first is the probability that the courier delivers the required items, the second is the probability he delivers too few, and the third is the probability the truck breaks down.
Example 1