{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDuring 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.\u003c/p\u003e\u003cp\u003eThe \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e 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.\u003c/p\u003e\u003cp\u003eThe three religions can coexist in peace if their descriptions form disjoint subsequences of the \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e. More formally, one can paint some of the characters of the \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e in three colors: $$$1$$$, $$$2$$$, $$$3$$$, so that each character is painted in \u003cspan class\u003d\"tex-font-style-underline\"\u003eat most\u003c/span\u003e one color, and the description of the $$$i$$$-th religion can be constructed from the \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e by removing all characters that aren\u0027t painted in color $$$i$$$.\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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 \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e and the number of religion evolutions, respectively. The following line contains the \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e — a string of length $$$n$$$ consisting of lowercase English characters.\u003c/p\u003e\u003cp\u003eEach of the following line describes a single evolution and is in one of the following formats: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e $$$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. \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e $$$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. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYou can assume that no religion will have description longer than $$$250$$$ characters.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eWrite $$$q$$$ lines. The $$$i$$$-th of them should be \u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e if the religions could coexist in peace after the $$$i$$$-th evolution, or \u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e otherwise.\u003c/p\u003e\u003cp\u003eYou can print each character in any case (either upper or lower).\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 8\nabdabc\n+ 1 a\n+ 1 d\n+ 2 b\n+ 2 c\n+ 3 a\n+ 3 b\n+ 1 c\n- 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\nYES\nYES\nYES\nYES\nYES\nNO\nYES\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 8\nabbaab\n+ 1 a\n+ 2 a\n+ 3 a\n+ 1 b\n+ 2 b\n+ 3 b\n- 1\n+ 2 z\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\nYES\nYES\nYES\nYES\nNO\nYES\nNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, after the 6th evolution the religion descriptions are: \u003cspan class\u003d\"tex-font-style-tt\"\u003ead\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ebc\u003c/span\u003e, and \u003cspan class\u003d\"tex-font-style-tt\"\u003eab\u003c/span\u003e. The following figure shows how these descriptions form three disjoint subsequences of the \u003cspan class\u003d\"tex-font-style-underline\"\u003eWord of Universe\u003c/span\u003e:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/071eb8b42ad1c8eac4b91713c36f7a5b?v\u003d1725191505\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}