{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tA DNA sequence is composed of a series of four possible nucleobases, namely Adenine, Guanine, Thymine and Cytosine; we will refer to each of these bases by their initial. For our purposes, nucleobases have an associated cyclic ``order\u0026#39;\u0026#39;: \u003ctt\u003eA\u003c/tt\u003e is followed by \u003ctt\u003eG\u003c/tt\u003e, which in turn is followed by \u003ctt\u003eT\u003c/tt\u003e, which is followed by \u003ctt\u003eC\u003c/tt\u003e, which is followed by \u003ctt\u003eA\u003c/tt\u003e again. State-of-the-art research in genomics has revealed the startling fact that many diseases are caused by certain subsequences of bases not forming a palindromic sequence! Your mission as a leading researcher at ICPC laboratories is to take a DNA string \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e and a series of subsets \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e,..., \u003ci\u003eP\u003c/i\u003e\u003csub\u003et\u003c/sub\u003e\u003c/span\u003e of indices to characters (nucleobases) in \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e, and transform \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e so that each of the restrictions of the resulting string to \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e,..., \u003ci\u003eP\u003c/i\u003e\u003csub\u003et\u003c/sub\u003e\u003c/span\u003e are palindromic. (The restriction of \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e to a subset \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e \u003d {\u003ci\u003ei\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ei\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e,..., \u003ci\u003ei\u003c/i\u003e\u003csub\u003ek\u003c/sub\u003e}\u003c/span\u003e of indices, where \u003cspan class\u003d\"MATH\"\u003e0\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e\u003ci\u003ei\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u0026lt; \u003ci\u003ei\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u0026lt;...\u0026lt; \u003ci\u003ei\u003c/i\u003e\u003csub\u003ek\u003c/sub\u003e \u0026lt; | \u003ci\u003eS\u003c/i\u003e|\u003c/span\u003e, is the string \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003csub\u003ei\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003ci\u003eS\u003c/i\u003e\u003csub\u003ei\u003csub\u003e2\u003c/sub\u003e\u003c/sub\u003e...\u003ci\u003eS\u003c/i\u003e\u003csub\u003ei\u003csub\u003ek\u003c/sub\u003e\u003c/sub\u003e\u003c/span\u003e). It is possible to inspect any base of \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u003c/i\u003e\u003c/span\u003e at will, but only three transformations can be applied to a base:\u003c/p\u003e\r\n\u003col\u003e\r\n\t\u003cli\u003e\r\n\t\tLeave it unaltered.\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tIncrease it by \u003cspan class\u003d\"MATH\"\u003e1\u003c/span\u003e in the cyclic order of nucleobases (e.g. turn \u003ctt\u003eC\u003c/tt\u003e into \u003ctt\u003eA\u003c/tt\u003e).\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\tDecrease it by 1 (e.g. turn \u003ctt\u003eT\u003c/tt\u003e into \u003ctt\u003eG\u003c/tt\u003e).\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cp\u003e\r\n\tMoreover, owing to limitations of current technology, it is impossible to modify two bases in consecutive positions of the sequence. Is our goal achievable?\u003c/p\u003e\r\n\u003cp\u003e\r\n\tBy way of example, consider DNA sequence \u003ctt\u003eAGTAT\u003c/tt\u003e. Number positions starting from \u003cspan class\u003d\"MATH\"\u003e0\u003c/span\u003e, and suppose we have the three subsets \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003d {1, 4}\u003c/span\u003e, \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003d {0, 1}\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e3\u003c/sub\u003e \u003d {0, 2, 4}\u003c/span\u003e. One solution is to increase the first character and decrease the last, yielding \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u0026#39;\u003c/i\u003e \u003d GGTAG\u003c/span\u003e. The restrictions of \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eS\u0026#39;\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eP\u003c/i\u003e\u003csub\u003e3\u003c/sub\u003e\u003c/span\u003e are \u003ctt\u003eGG\u003c/tt\u003e, \u003ctt\u003eGG\u003c/tt\u003e and \u003ctt\u003eGTG\u003c/tt\u003e, respectively; all of them are palindromic.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tOne case where no solution is possible is when the string is \u003ctt\u003eCATGC\u003c/tt\u003e, and we require the subsequences determined by positions \u003cspan class\u003d\"MATH\"\u003e{0, 3}\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e{3, 4}\u003c/span\u003e be palindromic. Here, characters \u003cspan class\u003d\"MATH\"\u003e3\u003c/span\u003e, \u003cspan class\u003d\"MATH\"\u003e0\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e4\u003c/span\u003e would all need to become a \u003ctt\u003eT\u003c/tt\u003e. But this entails modifying consecutive characters \u003cspan class\u003d\"MATH\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e4\u003c/span\u003e, which is not allowed.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe first line of each test case has two integers \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e ( \u003cspan class\u003d\"MATH\"\u003e1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eN\u003c/i\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e10\u0026nbsp;000, 1\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eT\u003c/i\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e6\u0026nbsp;000\u003c/span\u003e), the sequence length and number of subsets to consider. The next line contains the DNA sequence of length \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e, all of whose characters are in \u003ctt\u003eACGT\u003c/tt\u003e. The subsets are described by the following \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e lines. Each line starts by ``\u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eL\u003c/i\u003e\u003c/span\u003e:\u0026#39;\u0026#39;, where \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eL\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"MATH\"\u003e(0\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eL\u003c/i\u003e\u003cimg align\u003d\"MIDDLE\" alt\u003d\"$ \\le$\" border\u003d\"0\" height\u003d\"31\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/4958img1.png\" width\u003d\"18\" /\u003e\u003ci\u003eN\u003c/i\u003e)\u003c/span\u003e is the number of positions in the subset, and is followed by \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e distinct integers between \u003cspan class\u003d\"MATH\"\u003e0\u003c/span\u003e and \u003cspan class\u003d\"MATH\"\u003e\u003ci\u003eN\u003c/i\u003e - 1\u003c/span\u003e in increasing order. Subsets may overlap partially or totally.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tA blank line separates different test cases. The input file is terminated by a line containing `\u003ctt\u003e0 0\u003c/tt\u003e\u0026#39;.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tIn a single line per test case, print `\u003ctt\u003eYES\u003c/tt\u003e\u0026#39; if the task is solvable and `\u003ctt\u003eNO\u003c/tt\u003e\u0026#39; otherwise.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e5 3\r\nAGTAT\r\n2: 1 4\r\n2: 0 1\r\n3: 0 2 4\r\n\r\n5 3\r\nCATGC\r\n0:\r\n2: 0 3\r\n2: 3 4\r\n\r\n0 0\r\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eYES\r\nNO\r\n\u003c/pre\u003e"}}]}