Three Religions
Contest: Codeforces Round 556 (Div. 1)
Difficulty rating: 2200
Tags: dp, implementation, strings

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.

Input format:
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.

Output format:
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).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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:

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

Example output:
YES
YES
YES
YES
YES
YES
NO
YES

Example input:
6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z

Example output:
YES
YES
YES
YES
YES
NO
YES
NO

Editorial:
For our convenience, construct a two-dimensional helper array $$$N$$$ where $$$N(i, c)$$$ is the location of the first occurrence of character $$$c$$$ in the Word of Universe on position $$$i$$$ or later (or $$$\infty$$$ if no such character exists). This array can be created in a straightforward in $$$O(26 \cdot n)$$$ time, by iterating the word from the end to the beginning.
Example. Consider the Word of Uniwerse equal to abccaab. The helper array looks as follows:
Actually, for our purposes it's easier to set $$$\infty = n$$$ (in our example, $$$n=7$$$) and also consider additional links from indices $$$n$$$ and $$$n+1$$$ to index $$$\infty = n$$$. Why? We'll later need the index of the first occurrence of some character after some location $$$p$$$. If this $$$p$$$ already happens to be $$$\infty$$$ ($$$n$$$, as we already established), we can easily see that no requested occurrence exists:
Let's now try to answer each query in $$$O(250^3)$$$ time. We can do it using dynamic programming: let $$$D(n_1, n_2, n_3)$$$ be the length of the shortest prefix of the Word of Universe that contains the disjoint occurrences of the prefix of length $$$n_1$$$ of the first religion's description, the prefix of length $$$n_2$$$ of the second religion's description, and the prefix of length $$$n_3$$$ of the third religion's description. Each state can be evaluated in constant time by checking for each religion $$$i \in \{1, 2, 3\}$$$, what the prefix length would be if the last character of the prefix is a part of the $$$i$$$-th religion's description. (We use the helper array $$$N$$$ to speed up the search.)
How to write the state transitions? For each $$$i \in \{1, 2, 3\}$$$: chop the last character of the $$$i$$$-th description's prefix, find the shortest prefix of the Word of Universe containing all three descriptions, and then reappend this last character. We can do that using our helper array:
$$$D(n_1, n_2, n_3) = \min \begin{cases} N(D(n_1 - 1, n_2, n_3) + 1, \text{description}_1[n_1]) & \text{if } n_1 \geq 1, \\ N(D(n_1, n_2 - 1, n_3) + 1, \text{description}_2[n_2]) & \text{if } n_2 \geq 1, \\ N(D(n_1, n_2, n_3 - 1) + 1, \text{description}_3[n_3]) & \text{if } n_3 \geq 1. \end{cases}$$$
Now, if the lengths of the descriptions are $$$\ell_1$$$, $$$\ell_2$$$, and $$$\ell_3$$$, respectively, then the embedding of these descriptions as distinct subsequences exists if and only if $$$D(\ell_1, \ell_2, \ell_3) < \infty = n$$$.
However, due to the nature of queries, we can do a single update in $$$O(250^2)$$$ time: if we drop a character, we don't need to recompute any states; if we add a character to the $$$i$$$-th description, we only need to recompute the states with $$$n_i$$$ equal to the length of the description — and there are at most $$$251^2$$$ of them! This allows us to solve the problem in $$$O(q \cdot 250^2)$$$ time.