Description

Xiao E likes to play card games with the teacher in different ways. Recently, they invented a new mode called "Gou Dan and Er Wu Zai".

The rules are as follows:

At the start of the game, Xiao E and the teacher each have $30$ HP, and each has $2$ cards in hand. All cards are identical. Each player may place cards in front of themselves; initially, there are no cards on either side.

The two players take turns to act. At the beginning of each of a player's turns, they first draw one card. The operation "draw one card" means: if the number of cards in hand is less than $3$, take one more card into the hand; if the hand already has exactly $3$ cards, then no more cards can be drawn. There are $4$ types of actions.

• Skill. Decrease your own HP by $2$, then draw one card.

• Attack. Specifically, the player may choose a card in front of themselves that has not attacked yet this turn, and either choose one card in front of the opponent to perish together, or choose a card in front of themselves that has not attacked yet this turn to make the opponent's HP decrease by $3$. If it is the latter, mark the chosen card as having attacked.

• Play a card. You may do this only if the number of cards in front of you is less than $4$ and you have at least one card in hand. First perform the following process $3$ times:

  • Randomly choose a character and decrease its HP by $1$. This character can be yourself, the opponent, or a card in front of either side. If there are a total of $k$ cards on the field (both sides combined), then the probability of choosing any particular character is $\frac{1}{k + 2}$. If the chosen character is a card and its HP becomes $0$, destroy it. If the chosen character is a player and their HP becomes $0$, that player immediately loses the game.

  After the $3$ times are completed, place one card from your hand in front of yourself. The card's HP is $2$. This card is considered to have already attacked during this turn.

• End the turn; then it becomes the opponent's turn.

Within one turn, a player may perform multiple actions, but the sum of the number of Skill actions and Play-a-card actions cannot exceed $O$. Except for ending the turn, there is no restriction on the order of these actions. For example, you may play a card first, then use Skill, then play another card. Before ending the turn, the player must perform at least one action of any type in that turn.

At any moment, if a player's HP is less than or equal to $0$, then that player loses the game.

After several turns, it is now just before the start of Xiao E's turn. Xiao E wants you to analyze: if both sides adopt optimal strategies, what is the probability that Xiao E wins from now on.

Input Format

The first line contains two positive integers $T, O$, representing the number of test cases and the upper limit of the number of Skill actions plus Play-a-card actions in each turn.
For each test case, the first line contains two positive integers $E, S$, representing Xiao E's and the teacher's current HP. It is guaranteed that $1 \le E, S \le 20$.
The second line contains a non-negative integer $c$, followed by $c$ positive integers $a_1, \ldots , a_c$, indicating that there are $c$ cards in front of the teacher, with HP values $a_1, \ldots , a_c$. It is guaranteed that $0 \le c \le 4$, $1 \le a_i \le 2$.
The third line contains a non-negative integer $p$, followed by $p$ positive integers $e_1, \ldots , e_p$, indicating that there are $p$ cards in front of Xiao E, with HP values $e_1, \ldots , e_p$. It is guaranteed that $0 \le p \le 4$, $1 \le e_i \le 2$.
The fourth line contains two non-negative integers in $[0, 3]$, representing the number of cards in hand of the teacher and Xiao E, respectively.
Before you arrived, the teacher may have cheated; you do not need to verify whether the input state can really occur after several rounds of the game.

Output Format

For each test case, output one real number per line, representing the probability that Xiao E wins when both sides make optimal decisions. Your answer is considered correct if its absolute error from the standard answer does not exceed ${10}^{-6}$.

1 5
1 1
0
0
0 1

0.500000000

1 4
5 14
1 1
1 1
1 0

0.041879441

Hint

[Sample Explanation #1]

At the start of the turn, Xiao E draws one card. Now Xiao E has $2$ cards in hand, the teacher has no cards in hand, and there are no cards in front of either side. Both players have HP equal to $1$. Under optimal play, Xiao E cannot use Skill, because after using it his HP would be less than or equal to $0$ and he would lose immediately; Xiao E cannot attack, because he has no cards in front of him; Xiao E also cannot end the turn, because he has not performed any action this turn yet. Therefore, Xiao E's optimal strategy is to play a card. Then a character among Xiao E and the teacher is randomly chosen, and that character's HP decreases by $1$ and they lose the game. So Xiao E's winning probability is $0.5$.

[Subtasks]

It is guaranteed that $1 \le T \le 351493, 3 \le O \le 5$.

[Afterword]

In the end, Xiao E still defeated the teacher.

"Teacher, once you play enough Warlock you will know how to play it. You still haven't played enough."

"Is bragging done like this nowadays? Bro, do you know how many Warlock wins I have, huh? I'm telling you, there isn't a single person in the world with more Warlock wins than me."

[Source]

From the preliminary contest of the 2021 Tsinghua University Student Algorithm Contest and Collegiate Invitational (THUPC2021).

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5