小兔子和小马最近学习了摩尔斯电码，发现仅用点和划这两个符号就可以表达无数的单词，因为每个字母都有其独特的点划字符串对应关系。小兔子和小马得出了错误的结论，因为一个点划字符串并不一定对应一个字母，它也可能对应一个数字，或者对应一个表示开始、中断和结束的句子。

无论如何，他们计划用 0 表示点，用 1 表示划，并用二进制字符串来表达他们自己的“快乐摩尔斯电码”。他们为每个字母随机分配了一个二进制字符串，并将其制成了一本密码本。

给定一个二进制字符串，小兔子和小马的密码本能否唯一地解释该字符串的含义？如果可以，输出 happymorsecode；如果有多种可能的解释，输出 puppymousecat 以及可行解释的数量（对 128 取模）；如果完全无法解释，输出 nonono。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 对于每个测试用例：第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $m$ ($1 \le m \le 26$)，分别表示给定二进制字符串 $s$ 的长度和密码本中字母的数量。接下来的 $m$ 行，每行包含一个唯一的字母及其对应的二进制字符串 $t$ ($1 \le |t| \le 5$)，其中 $|t|$ 表示字符串 $t$ 的长度。最后一行包含给定的二进制字符串 $s$。 保证所有 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，在一行中输出以下内容：如果密码本能唯一地解释该字符串的含义，输出 happymorsecode；如果密码本能对该字符串做出多种解释，输出 puppymousecat 以及可行解释的数量（对 128 取模）；如果该字符串完全无法解释，输出 nonono。

样例

样例输入 1

3
4 2
a 01
b 10
0110
4 4
a 01
b 10
c 01
d 0110
0110
4 2
a 1
b 10
0110

样例输出 1

happymorsecode
puppymousecat 3
nonono