动物朋友 Animal Companion

标签：ACG

题目背景

小鞄和薮猫去隔壁岛度假了，为了让大图书馆不那么空，白脸角鸮博士和雕鸮助手想要提高加帕里公园 friends 的姿势水平。她们决定首先教 friends 字符串，博士预定明天教授**AC自动机**。

显然，为了讲解需要，博士需要一个样例，于是博士把这个工作交给助手，让她从小鞄留下的书中随便选几个单词出来。助手从书里面随便取了几个单词作为模板串，但因为助手忙着摸鱼，她实在是不想花时间来构造一个符合人类语法的文本串。于是她把书中的字母挑了出来，然后把这个工作扔给了在河边摸鱼的另一名 friends 小爪水獭。但小爪水獭成天除了塔诺西并不会什么东西，于是她找到了公园的企鹅偶像组合 Pepapu，Pepapu 忙着写歌，她们并没有时间来管这些破事，但偶像的身份要求她们不能把锅甩给别人。

题目描述

皇家企鹅团长想到了一个绝妙的方法，她们把地面上一个区域分成了 K 份，每份代表一个字符。她们准备了很多鱼，每次往这个区域里面扔一条鱼，然后把鱼落到的区域代表的字符加到字符串末尾，这样就可以简单的构成文本串 S 了。
虽然接下了这个锅，但 Pepapu 并不想听博士讲课，她们希望博士讲课失败，这样她们就可以趁着当时人多开一场演唱会，发表她们的新专辑了。

显然，**当文本串 S 不包含任何一个模板串 P 时**，博士的样例等于没给，这样的讲课是失败的。

Pepapu 想知道博士用她们构造出的字符串讲课失败的概率。然而她们并不会计算，于是她们找到了公园的向导机器人，LuckyBeast。然而 Luckybeast 里并没有这样的程序，由于公园的管理者 Yonda 忙于后缀数组，因此他把这个任务交给了你，你需要更新 Luckybeast 的程序， 来回答 Pepapu 的问题。

输入格式

第一行包含一个整数 \(T\)，表示询问次数
对于每一次询问：

• 第一行包含一个整数 \(K\)，表示助手准备的的模板串的个数
• 接下来 \(K\) 行，每行包含一个字符串 \(P\)，表示Pepapu丢出的一个模板串
• 然后一个整数 \(N\)，表示可能出现的字符的个数
• 接下来 \(N\) 行，每行给出一个字符和其出现的概率
• 最后一个整数 \(L\)，表示 Pepapu 丢鱼丢出的文本串的长度

输出格式

第一行一个字符串，回答：小爪水獭的学名是？（输出样例中答案由 "xxxxx" 替代）
对于每次询问，输出单独一行一个整数，表示博士讲课失败的概率，保留六位小数

样例

Input

2

1
a
2
a 0.5
b 0.5
2

2
ab
ab
2
a 0.2
b 0.8
2

Output

0.250000
0.840000

数据范围

对 \(20\%\) 的数据，助手只提供了一个模板串
对另外 \(20\%\) 的数据，文本串与模板串长度相等
对 \(100\%\) 的数据，字符均为大小写字母或数字，所有模板串长度均不大于100，并有 \(T \le 50, K \le 20,L \le 100\)

注意

如果你的答案与标准答案的误差小于 \( 1e-2 \) 你将得到 2 分
如果你的答案与标准答案的误差小于 \( 1e-3 \) 你将得到 4 分
以此类推