描述

在任何语言中，某些字母组合都不会出现（或者至少出现得如此之少，以至于可以被认为不存在）。例如，英语中不存在包含三个字母组合“$buv$”的单词。给定一个不存在的字母组合列表，一种语言中可能的“单词”数量可以大大减少（这里的“单词”是指不包含任何给定字母组合作为子串的任意字母组合）。如果我们按照长度递增的顺序对所有这样的单词进行排序，对于相同长度的单词按字母顺序排序，我们可以从$1$开始对它们进行编号。假设字母表始终由小写字母“$a$”到“$z$”组成。

例如，如果列表中只包含“$q$”、“$ab$”和“$aaa$”这样的组合，单词的编号方式如下：

$1.a$

$2.b$

...

$16.p$

$17.r$

...

$26.aa$

$27.ac$

...

$649.zz$

$650.aac$

给定字母组合列表，编写一个程序，对于给定的单词输出其编号，对于给定的编号输出其单词。你可以假设没有任何单词会超过$20$个字符，也没有编号会大于$2{,}000{,}000{,}000$（输入和输出均适用）。

输入

输入包含多个测试用例。单独的一行中给出测试用例的数量$T$。然后是$T$个测试用例。每个测试用例从一行包含两个整数$N$（字母组合的数量，非负，最多$1{,}000$）和$M$（针对该列表的查询数量，正数，最多$100$）开始。接下来是$N$行，每行包含一个小写字母组合（包含$1$到$3$个字母）。之后是$M$行，每行包含一个正整数或一个小写字母单词。如果是单词，它将不包含该测试用例列表中的任何字母组合。如果是数字，它将不会大于语言中的单词数量。

输出

对于每个查询，输出一行，包含单词对应的编号，或者编号对应的单词。

样例输入

2
3 4
q
ab
aaa
16
r
27
aac
7 2
a
b
c
d
ef
ghi
ijk
102345678
ksvfuw

样例输出

p
17
ac
650
xexgun
39174383

来源

2004年西北欧