Little E likes to play card games with his teacher. Recently, they invented a game called "Goudan and Erwuzai".

The rules are as follows: At the beginning of the game, both Little E and the teacher have 30 health points and 2 cards in their hands. All cards are identical. Each player can place cards in front of them; initially, there are no cards in front of either player.

Both sides take turns. At the beginning of their turn, a player first draws a card. The "draw a card" operation means: if the number of cards in hand is less than 3, draw one more card into the hand; if there are exactly 3 cards in hand, no more cards can be drawn. There are 4 types of operations:

• Skill: Decrease your own health by 2, then draw a card.
• Attack: Specifically, a player can choose a card placed in front of them that has not attacked this turn, and choose a card in front of the opponent to destroy both, or choose a card placed in front of them that has not attacked this turn to decrease the opponent's health by 3. If the latter is chosen, the selected card is marked as having attacked.
• Play a Card: If you have fewer than 4 cards in front of you and have cards in your hand, you can perform this operation. First, perform the following process 3 times:
  • Randomly select a character and decrease its health by 1. This character can be yourself, the opponent, or a card in front of either player. If there are a total of $k$ cards on the field, the probability of selecting any character is $\frac{1}{k+2}$. If the character is a card and its health becomes 0, it is destroyed; if the character is a player and their health becomes 0, that player loses the game immediately. After performing this 3 times, place a card from your hand in front of you. The card's health is 2. This card is considered to have attacked this turn.
• End Turn: The turn passes to the opponent.

In one turn, a player can perform multiple operations, but the sum of the number of "Skill" and "Play a Card" operations cannot exceed $O$. Except for ending the turn, there is no order restriction on these operations; for example, you can play a card, then use a skill, then play another card. Before ending the turn, a player must perform at least one operation.

If at any moment a player's health is less than or equal to 0, that player loses the game.

After several turns, it is now the beginning of Little E's turn. Little E wants you to help him analyze the probability of him winning if both sides play optimally.

Input

The first line contains two positive integers $T$ and $O$, representing the number of test cases and the maximum number of "Skill" and "Play a Card" operations per turn, respectively.

For each test case, the first line contains two positive integers $E$ and $S$, representing the current health of Little E and the teacher, respectively. 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, \dots, a_c$, representing the $c$ cards in front of the teacher, with health values $a_1, \dots, a_c$. It is guaranteed that $0 \le c \le 4$ and $1 \le a_i \le 2$.

The third line contains a non-negative integer $p$, followed by $p$ positive integers $e_1, \dots, e_p$, representing the $p$ cards in front of Little E, with health values $e_1, \dots, e_p$. It is guaranteed that $0 \le p \le 4$ and $1 \le e_i \le 2$.

The fourth line contains two non-negative integers between 0 and 3, representing the number of cards in the teacher's hand and Little E's hand, respectively.

The teacher may have cheated before you arrived; you do not need to determine whether the input state is a valid state reached after several turns of the game.

Output

For each test case, output a single real number representing the probability that Little E wins when both sides play optimally. Your output is considered correct if the absolute error from the standard answer does not exceed $10^{-6}$.

Examples

Input 1

1 1 5
2 1 1
3 0
4 0
5 0 1

Output 1

0.500000000

Note

At the start of the turn, Little E draws a card. At this point, Little E has 2 cards in hand, the teacher has 0 cards, and there are no cards in front of either player. Both players have 1 health point. Under optimal strategy, Little E cannot use a skill because doing so would result in his health becoming less than or equal to 0, causing him to lose the game; Little E cannot attack because there are no cards in front of him; Little E cannot end the turn because he has not performed any operations this turn. Therefore, Little E's optimal strategy is to play a card, which will randomly select either Little E or the teacher, decrease their health by 1, and cause them to lose the game. Thus, Little E's winning probability is 0.5.