Codenames 是一款流行的桌面游戏。两支队伍通过各自的“情报员”（spymaster）给出单字线索进行竞争，这些线索可以指向棋盘上的多个词。队伍中的其他玩家尝试猜出属于自己队伍的词，同时避开对方队伍的词。游戏的目标是成为第一支将本队所有词揭示出来的队伍。

玩家分为红队和蓝队。每队选出一名玩家担任情报员，其余玩家为现场特工。

棋盘上排列着 $N$ 张代号卡，每张卡上都有一个词。每个词代表以下身份之一：红队特工、蓝队特工、刺客或无辜路人。所有玩家都能看到所有的代号词，但只有情报员知道这些卡的身份。

双方轮流进行。在每一轮中，相应的情报员会给出关于各自卡片上词语的口头提示。每个提示只能由一个单词和一个数字组成。情报员的提示应尽可能贴近本队特工的卡片。提示中的数字告诉现场特工最多可以进行多少次猜测。

情报员给出提示后，现场特工会对哪些代号卡与提示相关进行猜测，并逐一指出。当一张代号卡被指出时，情报员会揭示该卡的身份——蓝队特工卡、红队特工卡、无辜路人卡或刺客卡。根据卡的身份，会发生以下情况之一： 如果指出的是刺客，游戏立即结束，该队失败。 如果指出的是无辜路人，回合直接结束。 如果指出的是对方队伍的特工，回合结束，对方队伍距离胜利更近一步。 如果指出的是本队的特工，他们距离胜利更近一步，并且可以选择进行下一次猜测。

当一方队伍的所有特工都被识别出来时（该队获胜），或者当一方队伍识别出刺客时（该队失败），游戏结束。

为了简化问题，假设两队共享相同的提示词字典及其与代号卡的关联。例如，考虑这个棋盘（$N = 6$）： Plate(R) Screen(I) Novel(A) Robin(B) Iron(R) Server(B) （R：红队特工；B：蓝队特工；I：无辜路人；A：刺客）

提示词及其关联的代号卡列表如下： Alfred Robin, Server, Plate Net Server, Screen, Plate Computer Screen, Server Twitter Screen, Robin, Server Crusoe Robin, Novel Film Iron, Screen

一旦情报员给出了提示词和一个数字 $K$（$1$ 到与该提示相关的未揭示词数量之间的整数），现场特工就会从尚未揭示的关联词列表中进行随机猜测（等概率）。他们将继续猜测，直到发生以下情况之一：（1）他们猜中了 $K$ 次，（2）他们赢得了游戏，或（3）他们的回合以猜错结束。他们永远不会在列表之外进行猜测，也不会使用前几轮的提示。如果某个提示词的所有关联代号卡都已被揭示，情报员给出该提示词是非法的。所有提示词都可以被任一队伍多次使用。

例如，假设蓝队在第一轮先手，蓝队情报员可能会给出提示“Twitter, 2”。蓝队猜中“Screen”、“Robin”和“Server”的概率各为 $1/3$。如果他们碰巧猜中了“Screen”，由于该词是无辜路人，他们的回合结束。否则，他们猜中了一个词，并将以 $1/2$ 的概率在剩余的两个词中进行下一次猜测。无论选择如何，他们的回合将在这次猜测后结束，红队将开始他们的回合，由红队情报员给出提示。

现在你被选为情报员，你的队伍（颜色在输入中指定）先手。假设双方情报员都采取最优策略，你获胜的概率是多少？

输入格式

第一行包含一个整数和一个字符，由空格分隔。整数 $N$ ($1 \le N \le 15$) 是棋盘的大小。字符为 R 或 B，表示你的队伍（红色或蓝色）。

第二行包含 $N$ 个不同的单词，由空格分隔。每个单词由最多 20 个小写英文字母组成。

第三行包含 $N$ 个单字符字符串，由空格分隔。第 $i$ 个字符串表示第 $i$ 个词的身份，含义如下：R——红队特工；B——蓝队特工；I——无辜路人；A——刺客。红队特工词和蓝队特工词各有一个或多个，无辜路人和刺客词有零个或多个。

第四行包含一个整数 $M$ ($1 \le M \le 50$)，即提示词的数量。

接下来的 $M$ 行，每行包含一个整数 $H_i$ ($1 \le H_i \le N$)，后跟 $H_i$ 个不同的单词，由空格分隔。它描述了与第 $i$ 个提示词关联的代号卡。保证所有单词都会出现在棋盘上。

输出格式

输出你获胜的概率。如果你的答案与裁判数据的绝对误差不超过 $10^{-4}$，则被视为正确。

样例

输入 1

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

输出 1

0.5000

说明 1

蓝队情报员有三个提示词可供选择（在任何情况下，他们的队伍在一回合中只能进行一次猜测，因此 $K$ 的选择无关紧要）： 1. 如果他们选择第一个，他们的队伍有 $1/2$ 的概率猜中“apple”并赢得游戏，有 $1/2$ 的概率猜中“java”并结束回合，这使得红队情报员可以给出第三个提示词并获胜。因此，在这种情况下，蓝队的获胜几率为 $1/2$； 2. 如果他们选择第二个，他们的队伍有 $1/2$ 的概率猜中“apple”并赢得游戏，有 $1/2$ 的概率猜中“dog”并输掉游戏。因此，蓝队的获胜几率也是 $1/2$； 3. 如果他们选择第三个，他们的队伍有 $1/2$ 的概率猜中“sleep”并输掉游戏，有 $1/2$ 的概率猜中“java”并结束回合，这使得红队情报员可以给出第三个提示词并获胜。因此，在这种情况下，蓝队的获胜几率为 $0$。

综上所述，蓝队情报员的最佳策略是（1）或（2），他们的获胜几率为 $1/2$。