403353: GYM101138 A Yet Another Problem with Strings

You are given an array with n strings S₀, S₁, ..., S_n - 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.

Let'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).

There are two types of queries.

The 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 S_i is a substring of the deciphered string. In a single line print YES or NO.

The 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}.

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 S₀, S₁, ..., S_n - 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.

For each query of the first type, print YES if there exists a string S_i that is a substring of the deciphered string t. Otherwise print NO (without the quotes).

5 7
aba
broadway
test
why
i
1 tst
1 text
2 1 2
1 caaabaaac
1 qbpqfkd
2 4 0
1 wdwdsdubaa

NO
NO
YES
YES
NO

The answer is NO for the queries 0 and 1 because no initial S_i is a substring of "tst" or "text".

In the query 2 a string S₁ is changed from "broadway" into "broadwayc".

In the query 3 the answer is YES because a string S₀ ("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 S₄ ("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 S₃ (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 S_i is its substring, so the answer is NO.