*【CodeForces - 1150D】Three Religions（dp，预处理，思维）

*【CodeForces - 1150D】Three Religions（dp，预处理，思维）

题干：

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: 11, 22, 33, so that each character is painted in at most one color, and the description of the ii-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color ii.

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.

Input

The first line of the input contains two integers n,qn,q (1≤n≤1000001≤n≤100000, 1≤q≤10001≤q≤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 nn consisting of lowercase English characters.

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

+ ii cc (i∈{1,2,3}i∈{1,2,3}, c∈{a,b,…,z}c∈{a,b,…,z}: append the character cc to the end of ii-th religion description.- ii (i∈{1,2,3}i∈{1,2,3}) – remove the last character from the ii-th religion description. You can assume that the pattern is non-empty.

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

Output

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

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

Examples

Input

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

Output

YESYESYESYESYESYESNOYES

Input

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

Output

YESYESYESYESYESNOYESNO

Note

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:

题目大意：

给一个1e5的串str，然后有三个起始空串，不超过1000次操作，对三个字符串的一个尾部加一个字符或者减一个字符，保证每个字符不会超过250

每次操作之后询问你这三个串是不是可以组成str的子序列，

比如ab,cd,ef可以组成acgbdef的子序列

解题报告：

[ i ][ j ] 代表的是在第j个位置之后的第i个字符的位置在哪里。

dp[ i ][ j ][ k ] 代表的是 匹配 第一个串前i个字符， 第二个串前j个字符， 第三个串前k个字符 这个状态时 最后面一个字符在原串的位置的最小值。

如果题目把三个串给你，那么就应该是个n^3的dp。

但是这题并没有这么善良，他的串是动态变化的。

比如，当操作为“+”的时候，如果添加的是s1，若s1的长度变为top[1]+1，可以发现，dp方程改变的只有dp [ top[1]+1] [ j ] [ k ] ，而其他的状态值都没有改变（因为只是在尾部操作，这点很关键）如果是s[2]也一样，就是dp [ i ] [ top[2] + 1 ] [ k ] 。

而当操作为"-"的时候，我们并不需要更新dp数组，还是假设操作对象是s1，我们只能用到dp [ top[1] - 1 ] [ j ] [ k ] ，而这之前已经处理好了，而假设我们下一次需要“+”，自然会覆盖dp [ top[1] ] [ j ] [ k ] 。所以不需要管。

对于某个字符下一次出现的位置，可以提前预处理出来。

所以总的复杂度为O(26n+250^2 * q)。

这题细节还是很多的。比如初始化的时候，需要初始化trie[n+1]  trie[n+2]这两维，因为后面更新的时候要用到。（当然 能否用到就取决于你设置的非法状态是多少，这里设置成n+1那么  代码汇总有可能用到 (n+1) + 1 这个状态的值，也就是n+2了，，所以也要对这一维进行初始化。）

其次不是所有erase操作都直接输出YES。因为万一我模板串是 'aa' ，然后我对1号串+了100次 ' a '，那我erase98次都应该输出NO才对。

AC代码：

#include#include#include#include#include

给几个样例理解一下dp，对每次询问可以输出一下dp[top[1]][top[2]][top[3]]的值看看。

/* 6 5 eabbcd + 1 a + 1 b + 2 b + 2 c + 3 e

6 5 eabbcd

+ 3 e + 1 a + 1 b + 2 b + 2 c

6 6 aaaaaa + 1 a + 1 a + 2 a + 2 a + 2 a + 3 a */

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。