403353: GYM101138 A Yet Another Problem with Strings

Memory Limit:256 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Yet Another Problem with Stringstime limit per test8 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

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 Si 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.

Input

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.

Output

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

ExamplesInput
5 7
aba
broadway
test
why
i
1 tst
1 text
2 1 2
1 caaabaaac
1 qbpqfkd
2 4 0
1 wdwdsdubaa
Output
NO
NO
YES
YES
NO
Note

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.

加入题单

上一题 下一题 算法标签: