405137: GYM101804 J JHADCBEIGF

The members from Incomprehensive Message Encryptors (IME) are learning a new cipher. This technique, although kinda weird, consists of using a key $$$k$$$ that is a permutation of the alphabet. In other words, if the alphabet $$$\Sigma$$$ is a sequence of $$$n$$$ symbols $$$a_1, a_2, …, a_n$$$, the key $$$k$$$ is a sequence of $$$n$$$ symbols $$$a_{p_1}, a_{p_2}, ... , a_{p_n}$$$, for some permutation $$$p_1, p_2, …, p_n$$$ of $$$1, 2, ... , n$$$.

They learned to use the key to encrypt a string $$$S$$$ by the following technique: for each $$$i$$$ in $$$1, 2, …, n$$$, they switch each occurrence of the character $$$a_i$$$ in the string $$$S$$$ by the corresponding character $$$a_{p_i}$$$ in the key $$$k$$$. This substitution occurs for all characters at once, so every substitution doesn’t influence the other ones.

For example, if $$$\Sigma = \{ A, B, C, D, E \}$$$ and $$$k = \{ E, D, C, A, B \}$$$, the encryption will change every symbol $$$A$$$ to $$$E$$$, $$$B$$$ to $$$D$$$, $$$C$$$ to $$$C$$$, $$$D$$$ to $$$A$$$ and $$$E$$$ to $$$B$$$. So the string $$$ABCBADE$$$ after encryption turns into $$$EDCDEAB$$$.

After learning the encryption, the members received $$$m$$$ tasks to execute. There are three types of tasks:

• $$$1$$$ $$$s$$$: add the string $$$s$$$ to the dictionary;
• $$$2$$$: for each string currently in the dictionary, change it by its encrypted version;
• $$$3$$$ $$$s$$$: check if the string $$$s$$$ is prefix of some string in the dictionary.

Because of how complex it is to encrypt it manually, and they are not really good at programming (by their incomprehensiveness), they need someone to solve these tasks for them. That’s why they gave you this responsibility.

The alphabet is always the first $$$n$$$ uppercase English letters in alphabetical order.

The first line of input contains two integers $$$n$$$, $$$m$$$ ( $$$1 \leq n \leq 26$$$, $$$0 \leq m \leq 10^5$$$) — the size of the alphabet and the number of tasks.

The second line contains one string $$$k$$$ ($$$|k| = n$$$) — the initial key. It's guaranteed that $$$k$$$ is a permutation of the alphabet.

The next $$$m$$$ lines contains, each, one integer $$$t_i$$$ ($$$1 \leq t_i \leq 3$$$) — the type of the task $$$i$$$.

If $$$t_i$$$ is $$$1$$$, the line also contains one string $$$s_i$$$ ($$$1 \leq |s_i| \leq 5 \times 10^5$$$) — the string to be added to the dictionary.

If $$$t_i$$$ is $$$3$$$, the line also contains one string $$$s_i$$$ ($$$1 \leq |s_i| \leq 5 \times 10^5$$$) — the string to be checked against the dictionary. It's guaranteed that $$$s_i$$$ only contains symbols from the alphabet.

It's guaranteed that there's at least one task of type $$$3$$$ and that $$$\sum{|s_i|} \leq 5 \ times 10^5$$$.

For each task of type $$$3$$$, print “YES” if the string is a prefix of some string in the dictionary, and “NO” otherwise.

5 10
ECABD
1 ABACABA
1 EAAE
2
1 AADE
3 ECEAECE
3 DED
2
3 EAAE
3 BDDB
3 AB

YES
NO
NO
YES
NO

5 12
BCDEA
1 AAAAA
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA
2
3 AAAAA

YES
NO
NO
NO
NO
YES