题目描述

许多大学采用百分制评分。每名学生最多可以获得 $100$ 分，其中：

• 平时成绩最多为 $75$ 分；
• 期末考试成绩最多为 $25$ 分。

学生的最终等级由平时成绩与考试成绩之和决定：

如果学生的平时成绩严格小于 $35$ 分，则没有资格参加考试。本题给出的学生均已获得考试资格，因此他们的平时成绩都在 $35$ 到 $75$ 之间。

按照名单从上到下依次写出所有学生的欧洲等级，并把它们首尾相接，可以得到一个字符串。例如，若连续三名学生的总分分别为 $92,75,66$，对应等级分别为 A、C、E，得到的字符串就是 ACE。

注意，等级 FX 会向字符串中依次加入两个字符 F 和 X。

考试结果具有随机性。对于每名学生，已知其获得 $0,1,\ldots,25$ 分考试成绩的概率。所有概率均以百分数表示，是非负整数，并且总和为 $100$。不同学生的考试成绩相互独立。

教师不希望最终得到的等级字符串中出现任何一个“不愉快字符串”作为连续子串。

请计算：最终等级字符串不包含任何不愉快字符串的概率。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

1. 第一行包含一个整数 $N$（$3\le N\le100$），表示学生人数。

2. 接下来 $N$ 行，每行包含 $27$ 个整数：

   • 第一个整数 $s$ 表示该学生的平时成绩，满足 $35\le s\le75$；
   • 随后的 $26$ 个整数 $p_0,p_1,\ldots,p_{25}$，其中 $p_j$ 表示该学生考试得到 $j$ 分的概率百分数。

   对每名学生均有：

   $$\sum_{j=0}^{25}p_j=100.$$

3. 下一行包含一个整数 $K$（$1\le K\le100$），表示不愉快字符串的数量。

4. 接下来 $K$ 行，每行包含一个不愉快字符串。

每个不愉快字符串：

• 只包含大写英文字母；
• 长度在 $2$ 到 $15$ 之间。

输出格式

对于每个测试用例，输出一行一个实数，表示教师满意的概率，单位为百分数。

答案可以使用任意标准浮点数格式输出。当相对误差不超过 $10^{-6}$ 时，答案将被认为正确。

样例输入

1
3
72 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 3 5 7 9 14 16 21 12 5 1
55 0 0 0 1 2 3 4 5 6 7 8 8 9 8 8 7 6 5 4 3 2 2 1 1 0 0
55 0 0 0 1 2 3 4 5 6 7 8 8 9 8 8 7 6 5 4 3 2 2 1 1 0 0
1
DE

样例输出

79.5

样例说明

第一名学生的总分至少为 $72+10=82$，因此其等级不可能为 D。

不愉快字符串 DE 出现，当且仅当：

• 第二名学生获得 $13\sim19$ 分，概率为 $41\%$；
• 第三名学生获得 $5\sim12$ 分，概率为 $50\%$。

因此 DE 出现的概率为

不出现的概率为

难度评定

约为 Codeforces 2400。