你是否曾遇到过这种情况？你正在与人愉快地交谈，突然想说一个你用过成百上千次的词，但这个词却从脑海中溜走了，只剩下你支支吾吾地吐出第一个音节。别担心，因为“对话停顿消除协会”（ICPC）已经开发出了一款软件来解决这个问题。

如果某个词就在你的嘴边，只需在 ICPC 软件中输入该词的前几个字符，它就会告诉你字典中有多少个词以这些字符作为前缀。ICPC 很快发现，他们的许多客户不仅有“话到嘴边”的问题，还有“词尾模糊”的问题，即用户只记得一个词的后缀。

为了尽可能提供帮助，ICPC 软件需要支持以下查询：

1. AND p s：统计字典中以 $p$ 为前缀且以 $s$ 为后缀的单词数量。
2. OR p s：统计字典中以 $p$ 为前缀或以 $s$ 为后缀的单词数量。
3. XOR p s：统计字典中以 $p$ 为前缀或以 $s$ 为后缀，但不同时满足这两个条件的单词数量。

单词的前缀和后缀可以是整个单词，也可以在单词内部重叠。由于 ICPC 软件的一个特性，$p$ 和 $s$ 的长度必须相同。你需要帮助软件开发者回答所有收到的查询。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \cdot 10^5$)，其中 $n$ 是字典中的单词数量，$q$ 是查询数量。

接下来的 $n$ 行，每行包含一个字符串 $w$，即字典中的一个单词。字典中的单词和查询中的所有字符均为小写拉丁字母（‘a’–‘z’）。字典中的所有单词各不相同。

接下来的 $q$ 行，每行包含三个字符串 $o$、$p$ 和 $s$，其中 $o$ 是操作符 ‘AND’、‘OR’ 或 ‘XOR’ 之一，$p$ 和 $s$ 是长度为 1 或以上的小写拉丁字母字符串，且满足 $|p| = |s|$。

字典和所有查询中的字符总数最多为 $10^6$；这不包括查询操作符 ‘AND’、‘OR’ 或 ‘XOR’、空格或换行符。换句话说，输入中最多有 $10^6$ 个小写字母。

输出格式

输出 $q$ 行，每行对应一个查询，按查询给出的顺序输出。每行输出一个整数，表示字典中匹配该查询的单词数量。

样例

样例输入 1

4 4
cat
catcat
octal
occidental
AND cat cat
OR oc at
AND ca at
XOR oc al

样例输出 1

2
4
2
0