在 Yandex LLC 的某个部门中，有 $N$ 名开发人员。每名开发人员都有一个他认为美观的字符串模式（模式由大写拉丁字母组成）。员工如果认为有必要，可以在个人主页上发布他最喜欢的模式。所有开发人员的模式长度均为 $L$。

如今，Git 是最流行的版本控制系统之一。特定的源代码版本（Git 术语中的提交）由一个由数字 $0$ 到 $9$ 和字母 $a$ 到 $f$ 组成的哈希字符串标识。如果一个哈希字符串在模式中字符相同的位置上也包含相同的字符，我们就说该哈希与给定的模式匹配。例如，哈希 1ac1ca1 与模式 ACEAOXA 和 ABCACBP 匹配。

有一天，部门主管 Peter 想知道有多少个 Git 哈希能与部门所有员工的模式匹配。他很快找到了答案。随后，他又对有多少个哈希能与特定项目组员工的模式匹配产生了兴趣。共有 $Q$ 个项目组，每个项目组都是该部门开发人员的一个子集。请根据每个团队的成员列表，找出同时与该团队所有成员的模式匹配的哈希数量。请以 $X \cdot 2^Y$ 的形式输出每个团队的结果，其中 $X$ 为奇数（例如，$48$ 应输出为 $3 \cdot 2^4$）。

输入格式

第一行包含两个整数 $N$ 和 $L$ ($1 \le N, L \le 200$)。接下来的 $N$ 行描述了 $N$ 个模式，其中第 $i+1$ 行包含第 $i$ 位员工最喜欢的模式。每个模式的长度均为 $L$，且由大写拉丁字母组成。

下一行包含一个整数 $Q$ ($1 \le Q \le 200$)。接下来的 $Q$ 行，每行包含一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串。如果第 $i$ 位开发人员 ($1 \le i \le N$) 属于当前字符串所描述的团队，则第 $i$ 个字符为 $1$，否则为 $0$。保证每行至少包含一个 $1$。

输出格式

对于每个项目组，输出与该团队所有成员最喜欢的模式相匹配的哈希数量。使用上述指定格式，并用字符 *2^ 分隔 $X$ 和 $Y$。

样例

输入 1

3 7
ABCDCBA
XXXTPPP
OAOAOAO
2
101
011

输出 1

1*2^8
1*2^4