{"raw_statement":[{"iden":"statement","content":"You are given an array with n strings S0, S1, ..., Sn - 1. You must process q queries, numbered 0 through q - 1. All strings in this problem are non-empty and consist of lowercase English letters.\n\nLet's create an integer variable _LAST_YES_ to decipher the input. As you process the queries in the given order, _LAST_YES_ should be equal to the index of the last query that was of the first type and had an answer _YES_. _LAST_YES_ is initially equal to 0. Note that _LAST_YES_ can't be changed in the first query because the index of the first query is 0 (note again that queries are numbered from 0 to q - 1).\n\nThere are two types of queries.\n\nThe first type is of ciphered form \"_1 t_\", where t is a string of lowercase English characters. Add _LAST_YES_ to each character in t (modulo 26) to get its deciphered value. For example, for a string _t = \"cdxyyz\"_ with _LAST_YES_ equal to 2, the deciphered string is _\"efzaab\"_. Then you should check whether at least one string Si is a substring of the deciphered string. In a single line print _YES_ or _NO_.\n\nThe second type is of ciphered form \"_2 i alpha_\" where i and alpha are integers. You should add a letter (alpha + LAST_YES)%26 at the end of S(i + LAST_YES)%n. Here we treat letters _'a'-'z'_ as numbers 0 - 25. For example, for alpha = 23 ans LAST_YES = 2604, you get (23 + 2604)%26 = 1, so you should add a letter _'b'_ at the end of S(i + LAST_YES)%n.\n\nThe first line of the input contains two integers n and q (1 ≤ n, q,  ≤ 200 000) — the size of the array S and the number of queries, respectively.\n\nThe next n lines contain strings S0, S1, ..., Sn - 1, one string per line. All strings are nonempty and consist of lowercase English letters. The total length of all n strings doesn't exceed 200 000.\n\nThe next q lines contain queries. Each query is of form \"_1 t_\" or \"_2 i alpha_\".\n\nFor the first type of query, t is a nonempty string of lowercase English letters. The total length of all t doesn't exceed 200 000.\n\nFor the second type, i and alpha are integers, and 0 ≤ i < n, 0 ≤ alpha < 26.\n\nFor each query of the first type, print _YES_ if there exists a string Si that is a substring of the deciphered string t. Otherwise print _NO_ (without the quotes).\n\nThe answer is _NO_ for the queries 0 and 1 because no initial Si is a substring of _\"tst\"_ or _\"text\"_.\n\nIn the query 2 a string S1 is changed from _\"broadway\"_ into _\"broadwayc\"_.\n\nIn the query 3 the answer is _YES_ because a string S0 (_\"aba\"_) is a substring of _\"caaabaaac\"_. _LAST_YES_ is equal to 3 now.\n\nThe query 4 asks about deciphered string _\"testing\"_ for which a string S4 (_\"i\"_) is a substring. LAST_YES is 4 now.\n\nThe query 5 asks to add a letter _'e'_ (because 0 + LAST_YES = 4) at the end of S3 (because (4 + LAST_YES)%n = 8%5 = 3). So, we change _\"why\"_ to _\"whye\"_.\n\nIn the last query a deciphered string t is _\"ahahwhyfee\"_ after the deciphering. None of Si is its substring, so the answer is _NO_.\n\n"},{"iden":"input","content":"The first line of the input contains two integers n and q (1 ≤ n, q,  ≤ 200 000) — the size of the array S and the number of queries, respectively.The next n lines contain strings S0, S1, ..., Sn - 1, one string per line. All strings are nonempty and consist of lowercase English letters. The total length of all n strings doesn't exceed 200 000.The next q lines contain queries. Each query is of form \"_1 t_\" or \"_2 i alpha_\".For the first type of query, t is a nonempty string of lowercase English letters. The total length of all t doesn't exceed 200 000.For the second type, i and alpha are integers, and 0 ≤ i < n, 0 ≤ alpha < 26."},{"iden":"output","content":"For each query of the first type, print _YES_ if there exists a string Si that is a substring of the deciphered string t. Otherwise print _NO_ (without the quotes)."},{"iden":"examples","content":"Input5 7ababroadwaytestwhyi1 tst1 text2 1 21 caaabaaac1 qbpqfkd2 4 01 wdwdsdubaaOutputNONOYESYESNO"},{"iden":"note","content":"The answer is _NO_ for the queries 0 and 1 because no initial Si is a substring of _\"tst\"_ or _\"text\"_.In the query 2 a string S1 is changed from _\"broadway\"_ into _\"broadwayc\"_.In the query 3 the answer is _YES_ because a string S0 (_\"aba\"_) is a substring of _\"caaabaaac\"_. _LAST_YES_ is equal to 3 now.The query 4 asks about deciphered string _\"testing\"_ for which a string S4 (_\"i\"_) is a substring. LAST_YES is 4 now.The query 5 asks to add a letter _'e'_ (because 0 + LAST_YES = 4) at the end of S3 (because (4 + LAST_YES)%n = 8%5 = 3). So, we change _\"why\"_ to _\"whye\"_.In the last query a deciphered string t is _\"ahahwhyfee\"_ after the deciphering. None of Si is its substring, so the answer is _NO_."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, q \\leq 200{,}000 $.  \nLet $ S = (S_0, S_1, \\dots, S_{n-1}) $ be a tuple of non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ \\text{LAST\\_YES} \\in \\mathbb{Z} $ be a state variable, initially $ \\text{LAST\\_YES} = 0 $.  \n\nLet $ Q = (q_0, q_1, \\dots, q_{q-1}) $ be a sequence of $ q $ queries, each of type 1 or 2:  \n- Type 1: $ q_j = (1, t_j) $, where $ t_j \\in \\Sigma^+ $  \n- Type 2: $ q_j = (2, i_j, \\alpha_j) $, where $ i_j \\in \\{0, \\dots, n-1\\} $, $ \\alpha_j \\in \\{0, \\dots, 25\\} $  \n\n**Constraints**  \n1. Total length of all $ S_i $: $ \\sum_{i=0}^{n-1} |S_i| \\leq 200{,}000 $  \n2. Total length of all $ t_j $ in type-1 queries: $ \\sum_{j: q_j \\text{ type 1}} |t_j| \\leq 200{,}000 $  \n3. For type-2 queries: $ 0 \\leq i_j < n $, $ 0 \\leq \\alpha_j < 26 $  \n\n**Operations**  \nFor each query $ j \\in \\{0, \\dots, q-1\\} $:  \n\n- **If type 1**:  \n  Let $ d_j $ be the deciphered string:  \n  $$\n  d_j[k] = \\left( t_j[k] - 'a' + \\text{LAST\\_YES} \\right) \\bmod 26 + 'a', \\quad \\forall k \\in \\{0, \\dots, |t_j|-1\\}\n  $$  \n  Output:  \n  $$\n  \\begin{cases}\n  \\text{YES} & \\text{if } \\exists i \\in \\{0, \\dots, n-1\\} \\text{ s.t. } S_i \\text{ is a substring of } d_j \\\\\n  \\text{NO} & \\text{otherwise}\n  \\end{cases}\n  $$  \n  Update:  \n  $$\n  \\text{LAST\\_YES} \\leftarrow \n  \\begin{cases}\n  j & \\text{if output is YES} \\\\\n  \\text{LAST\\_YES} & \\text{otherwise}\n  \\end{cases}\n  $$  \n\n- **If type 2**:  \n  Let $ \\delta = (\\alpha_j + \\text{LAST\\_YES}) \\bmod 26 $  \n  Let $ \\ell = (i_j + \\text{LAST\\_YES}) \\bmod n $  \n  Update:  \n  $$\n  S_\\ell \\leftarrow S_\\ell + \\left( \\delta + 'a' \\right)\n  $$  \n\n**Objective**  \nFor each type-1 query $ j $, output the corresponding YES/NO answer as defined above.","simple_statement":"You are given n strings and q queries. Two types of queries:\n\n1. \"1 t\": Decrypt string t by adding LAST_YES to each char (mod 26). Then check if any of the n strings is a substring of the decrypted t. Print \"YES\" or \"NO\".  \n2. \"2 i alpha\": Add letter (alpha + LAST_YES) % 26 to the end of string S[(i + LAST_YES) % n].\n\nLAST_YES starts at 0. It updates to the index of the last \"YES\" answer from type 1 queries. If no \"YES\" so far, it stays 0.\n\nTotal length of all strings and all t’s ≤ 200,000.","has_page_source":false}