CF1149B Three Religions

在中东的考古研究中，你发现了三种古老宗教的踪迹：第一宗教、第二宗教和第三宗教。你整理了每种信仰演变的信息，现在你想知道，这三种宗教的信徒是否能够和平共处。 宇宙之词是一个只包含小写英文字母的长字符串。在任意时刻，每种宗教的信仰都可以用一个只包含小写英文字母的字符串来描述。 如果三种宗教的描述可以分别作为宇宙之词的互不相交的子序列，则它们可以和平共处。更正式地说，你可以将宇宙之词中的某些字符分别涂成三种颜色：$1$、$2$、$3$，使得每个字符至多被涂一种颜色，并且第 $i$ 种宗教的描述可以通过从宇宙之词中删除所有未被涂成颜色 $i$ 的字符得到。 然而，宗教会不断演变。起初，每种宗教的描述都是空的。每次演变时，要么在某个宗教描述的末尾添加一个字符，要么从某个宗教描述的末尾删除一个字符。每次变化后，请判断三种宗教的描述是否能够和平共处。

第一行包含两个整数 $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$。

输出 $q$ 行，第 $i$ 行为 YES 表示第 $i$ 次演变后宗教描述可以和平共处，NO 表示不可以。 你可以用任意大小写输出 YES 或 NO。

在第一个样例中，第 6 次演变后，三种宗教的描述分别为：ad、bc 和 ab。下图展示了这些描述如何作为宇宙之词的三条互不相交的子序列：  由 ChatGPT 4.1 翻译