题目描述

ICPC 软件维护一个词典，并需要支持用户关于前缀和后缀的查询。

给定一个词典，接下来有若干询问。每个询问给出一个操作 $o$、一个前缀 $p$ 和一个后缀 $s$，并且保证 $|p|=|s|$。

需要回答以下三种查询之一：

1. AND p s：词典中同时以 $p$ 为前缀、以 $s$ 为后缀的单词数量；
2. OR p s：词典中以 $p$ 为前缀或以 $s$ 为后缀的单词数量；
3. XOR p s：词典中以 $p$ 为前缀或以 $s$ 为后缀，但不是两者同时满足的单词数量。

前缀和后缀可以是整个单词，也可以在同一个单词中重叠。

输入格式

第一行包含两个整数 $n,q$：

• $1 \le n,q \le 2\cdot 10^5$；
• $n$ 为词典中的单词数；
• $q$ 为询问数。

接下来 $n$ 行，每行一个字符串 $w$，表示词典中的一个单词。所有词典单词互不相同。

接下来 $q$ 行，每行包含三个字符串 $o,p,s$：

• $o$ 为 AND、OR 或 XOR；
• $p,s$ 均为非空小写字符串；
• $|p|=|s|$。

所有词典单词和询问中的字符均为小写英文字母。输入中的小写字母总数不超过 $10^6$，不包含操作名、空白符和换行。

输出格式

输出 $q$ 行，第 $i$ 行为第 $i$ 个询问的答案。

样例 #1

输入

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

输出

2
4
2
0