31310번 - Tip of Your Tongue 다국어

문제

Has this scenario ever happened to you? You're having a lovely conversation with someone, begin to say a word you've used hundreds of times, and the word escapes your mind, leaving you sputtering the first syllable. Well worry no more, because the Institute for Cancelling Pauses in Conversation (ICPC) has developed software to curtail this issue.

If there's a word on the tip of your tongue, enter the first few characters of the word into the ICPC software, and it will tell you how many words in the dictionary have those characters as a prefix. The ICPC quickly discovered that many of their clients don't only have tip-of-your-tongue problems, but also base-of-your-tongue problems, where users only remember some suffix of a word.

To be as useful as possible, the ICPC software needs to support the following queries:

1. AND $p$ $s$. Count the number of words in the dictionary that have $p$ as a prefix and $s$ as a suffix.
2. OR $p$ $s$. Count the number of words in the dictionary that have $p$ as a prefix or $s$ as a suffix.
3. XOR $p$ $s$. Count the number of words in the dictionary that have $p$ as a prefix or $s$ as a suffix, but not both.

Prefixes and suffixes of a word may be the whole world, and can overlap within the word. Due to a quirk in the ICPC software, $p$ and $s$ must be the same length. You must help the software developers answer all the incoming queries.

입력

The first line of input contains two integers $n$ and $q$ (1ドル \le n,q \le 2 \cdot 10^5$), where $n$ is the number of words in the dictionary and $q$ is the number of queries.

Each of the next $n$ lines contains a single string $w,ドル which is a word in the dictionary. All characters in dictionary words and queries are lowercase Latin characters ('a'--'z'). All words in the dictionary will be distinct.

Each of the next $q$ lines contains three strings $o,ドル $p,ドル and $s,ドル where $o$ is one of the operations 'AND', 'OR', or 'XOR', and $p$ and $s$ are strings of one or more lowercase Latin characters ('a'---'z') with $|p| = |s|$.

The total number of characters in the dictionary and across all queries is at most 10ドル^6$; this does not include query operations 'AND', 'OR', or 'XOR', whitespace, or newline characters. Said another way, there are at most 10ドル^6$ lowercase letters in the input.

출력

Output $q$ lines, one per query, in the order the queries were given. On each line output a single integer, which is the number of words in the dictionary that match that particular query.

제한

힌트