CF1149B.Three Religions

During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.

The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.

The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: $1$, $2$, $3$, so that each character is painted in at most one color, and the description of the $i$-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color $i$.

The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.

在中东的考古研究中，你发现了三种古代宗教的痕迹：第一宗教、第二宗教和第三宗教。你整理了每种信仰演化过程的相关信息，现在你想知道：这三种宗教的信徒能否和平共存？

《宇宙之词》（The Word of Universe）是一个仅由小写英文字母组成的长字符串。在任意时刻，每种宗教的教义均可由一个仅含小写英文字母的字符串来描述。

当这三种宗教的描述字符串构成《宇宙之词》的互不相交的子序列时，这三种宗教便能和平共存。更准确地说，我们可以将《宇宙之词》中的一些字符分别涂上三种颜色：$1$、$2$、$3$，要求每个字符至多被涂一种颜色，且第 $i$ 种宗教的描述字符串恰好可由《宇宙之词》中所有涂成颜色 $i$ 的字符按原有顺序拼接而成。

然而，这些宗教是不断演化的。初始时，每种宗教的描述字符串均为空。随后，会不断发生两类操作：要么向某一种宗教的描述字符串末尾追加一个字符，要么从某一种宗教的描述字符串末尾删去最后一个字符。每次操作后，请判断此时三种宗教是否仍能和平共存。

The first line of the input contains two integers $n, q$ ($1 \leq n \leq 100\,000$, $1 \leq q \leq 1000$) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length $n$ consisting of lowercase English characters.

Each of the following line describes a single evolution and is in one of the following formats:

• • $i$ $c$ ($i \in {1, 2, 3}$, $c \in {\mathtt{a}, \mathtt{b}, \dots, \mathtt{z}}$: append the character $c$ to the end of $i$-th religion description.
• - $i$ ($i \in {1, 2, 3}$) – remove the last character from the $i$-th religion description. You can assume that the pattern is non-empty.

You can assume that no religion will have description longer than $250$ characters.

输入的第一行包含两个整数 $n, q$（$1 \leq n \leq 100\,000$，$1 \leq q \leq 1000$），分别表示“宇宙之词”的长度以及宗教演化次数。
接下来的一行包含“宇宙之词”——一个长度为 $n$ 的、由小写英文字母组成的字符串。

随后的每一行描述一次演化，其格式为以下两种之一：

• + $i$ $c$（其中 $i \in \{1, 2, 3\}$，$c \in \{\mathtt{a}, \mathtt{b}, \dots, \mathtt{z}\}$）：将字符 $c$ 追加到第 $i$ 个宗教描述的末尾。
• - $i$（其中 $i \in \{1, 2, 3\}$）：从第 $i$ 个宗教描述中删除最后一个字符。题目保证执行该操作时对应宗教描述非空。

你可以假设任意宗教的描述长度均不会超过 $250$ 个字符。

Write $q$ lines. The $i$-th of them should be YES if the religions could coexist in peace after the $i$-th evolution, or NO otherwise.

You can print each character in any case (either upper or lower).

输出 $q$ 行。其中第 $i$ 行应为 YES（如果在第 $i$ 次演化后，这些宗教能够和平共存），否则为 NO。

每个字符的大小写均可（大写或小写均可）。

In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe:

在第一个例子中，经过第 6 次演化后，三种宗教的描述分别为：ad、bc 和 ab。下图展示了这些描述如何构成“宇宙之词”（Word of Universe）的三个互不相交的子序列：