在中东的考古研究中,您发现了三种古代宗教的痕迹:第一宗教、第二宗教和第三宗教。您收集了有关每种信仰演变的信息,现在您想知道每种宗教的追随者是否可以和平共处。
宇宙之词是一个仅包含小写英文字符的长词。在每个时刻,每种宗教信仰都可以用一个由小写英文字符组成的单词来描述。
如果这三种宗教的描述形成了宇宙之言的不相交的子序列,那么它们就可以和平共处。更正式地说,人们可以用三种颜色绘制宇宙之词的一些字符:$$$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。下图显示了这些描述如何形成宇宙之词的三个不相交的子序列: