Problem L
Codenames

Codenames is a popular board game. Two teams compete by each having a “spymaster” give one-word clues that can point to multiple words on the board. The other players on the team attempt to guess their team’s words while avoiding the words of the other team. The objective is to be the first team to have all their team’s words revealed.

Players split into two teams: red and blue. One player of each team is selected as the team’s spymaster; the others are field operatives.

$N$ Codename cards, each bearing a word, are laid out in a line. Each word represents one of the following: a red agent, a blue agent, an assassin, or an innocent bystander. All players can see all the Codename words, but only the spymasters know the identities of the cards.

Teams take turns. On each turn, the appropriate spymaster gives a verbal hint about the words on the respective cards. Each hint may only consist of one single word and a number. The spymaster’s hint should be as close to their own agents’ cards as possible. The hint’s number tells the field operatives the maximum number of guesses to make.

After a spymaster gives the hint, their field operatives make guesses about which Codename cards bear words related to the hint and point them out, one at a time. When a Codename card is pointed out, the spymaster reveals the identity of that card—a blue agent card, a red agent card, an innocent bystander card, or the assassin card. Depending on the identity of the card, one of these things happens:

• If an assassin is pointed out, the game ends immediately, and their team loses.

• If an innocent bystander is pointed out, the turn simply ends.

• If an agent of the other team is pointed out, the turn ends, and that other team is one agent closer to winning.

• If an agent of their team is pointed out, they are one agent closer to winning, and they may choose to make another guess.

The game ends when all of one team’s agents are identified (winning the game for that team), or when one team has identified the assassin (losing the game).

To simplify the problem, let’s assume that both teams share the same dictionary of hint words and their associations with Codename cards. For example, consider this board ($N=6$):

The list of hint words and their associated Codenames cards is given in Table 2.

Once the spymaster gives a hint word and a number, $K$ (an integer between 1 and the number of unrevealed words associated with the hint), their field operatives make random guesses—with equal probability—from the list of associated words that are not revealed yet. They will continue to make guesses until one of the following happens: (1) they get $K$ hits, (2) they have won the game, or (3) their turn ends with a miss. They will never make guesses outside the list or use hints from the previous rounds. It is illegal for the spymaster to give a hint word whose all associated Codename cards have already been revealed. All hint words can be used multiple times by either team.

For example, assuming the blue team goes first in the first round, the blue spymaster may give a hint “Twitter, 2”. The blue team has $1/3$ chance of guessing “Screen”, “Robin” and “Server”, respectively. If they happen to guess “Screen”, their turn ends as the word is an innocent bystander. Otherwise, they get a hit and will make another guess, with $1/2$ chance on either of the remaining two words. Regardless of the choice, their turn will end after this guess, and the red team will start their turn with the red spymaster giving a hint.

Now you are selected as the spymaster, and your team (color specified in the input) goes first. Assuming both spymasters play optimally, what is your probability of winning the game?

Input

The first line consists of an integer and a character, separated by a single space. The integer is $N$ ($1\le N\le 15$), the size of the board. The character is R or B, indicating your team (red or blue).

The second line consists of $N$ distinct words, separated by a single space. Each word consists of up to 20 lowercase English letters.

The third line consists of $N$ single-character strings, separated by a single space. The $i$-th string indicates the identity of the $i$-th word, with the following meaning: R—Red team’s agent; B—Blue team’s agent; I—Innocent bystander; A—Assassin. There are one or more “R” and “B” words, and there are zero or more “I” and “A” words.

The fourth line consists of an integer $M$ ($1\le M\le 50$), which is the number of hint words.

Each of the following $M$ lines consists of an integer $H_i$ ($1\le H_i\le N$), followed by $H_i$ distinct words separated by a single space. It describes the associated Codename cards with the $i$-th hint word. All words are guaranteed to appear on the board. Every “R” and “B” word on the board is associated with at least one hint.

Output

Probability of winning the game. Your answer will be considered correct if it has an absolute error of at most ${10}^{-4}$ with the judges’ data.

Sample Explanation

The blue spymaster has three hint words to choose from (in any case, their team can only make one guess in the turn, so the choice of $K$ does not matter):

1. If they choose the first, their team has $1/2$ probability of guessing “apple” and wins the game, and $1/2$ probability of guessing “java” and ends the turn, which allows the red spymaster to give the third hint word and win. So the blue team’s winning chance is $1/2$ in this case;

2. If they choose the second, their team has $1/2$ probability of guessing “apple” and wins the game, and $1/2$ probability of guessing “dog” and loses the game. So the blue team’s winning chance is also $1/2$;

3. If they choose the third, their team has $1/2$ probability of guessing “sleep” and loses the game, and $1/2$ probability of guessing “java” and ends the turn, which allows the red spymaster to give the third hint word and win. So the blue team’s winning chance is $0$ in this case.

To sum up, the best strategy for the blue spymaster is either (1) or (2) and their winning chance is $1/2$.

4 B
apple sleep java dog
B R I A
3
2 apple java
2 apple dog
2 sleep java

0.5000