← 返回题目列表

Codeforces · 1149/B

B. 三种宗教

中文机器翻译题面 查看原题

在中东的考古研究中,您发现了三种古代宗教的痕迹:第一宗教、第二宗教和第三宗教。您收集了有关每种信仰演变的信息,现在您想知道每种宗教的追随者是否可以和平共处。

宇宙之词是一个仅包含小写英文字符的长词。在每个时刻,每种宗教信仰都可以用一个由小写英文字符组成的单词来描述。

如果这三种宗教的描述形成了宇宙之言的不相交的子序列,那么它们就可以和平共处。更正式地说,人们可以用三种颜色绘制宇宙之词的一些字符:$$$1$$$、$$$2$$$、$$$3$$$,以便每个字符最多用一种颜色绘制,并且可以通过删除所有未用 $$$i$$$ 颜色绘制的字符,从宇宙之词构建第 $$$i$$$ 宗教的描述。

然而,宗教不断发展。一开始,每种宗教的描述都是空洞的。每隔一段时间,就会在单个宗教的描述末尾添加一个字符,或者从描述中删除最后一个字符。每次改变后,确定宗教是否可以和平共处。

输入

输入的第一行包含两个整数 $$$n, q$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1 \leq q \leq 1000$$$) — 分别是宇宙之词的长度和宗教进化的数量。以下行包含 Word of Universe — 长度为 $$$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$$$ 次进化后能够和平共处,那么第 $$$i$$$ 次应该为“是”,否则为“否”。

您可以以任何大小写(大写或小写)打印每个字符。

示例

输入 #1

6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2

输出 #1

YES
YES
YES
YES
YES
YES
NO
YES

输入 #2

6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z

输出 #2

YES
YES
YES
YES
YES
NO
YES
NO

注意

在第一个示例中,第六次进化后的宗教描述为:ad、bc 和 ab。下图显示了这些描述如何形成宇宙之词的三个不相交的子序列: