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.
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.
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).
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_.
## 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).
[samples]
## 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_.
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ with $ 1 \leq n, q \leq 200{,}000 $.
Let $ S = (S_0, S_1, \dots, S_{n-1}) $ be a tuple of non-empty strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $.
Let $ \text{LAST\_YES} \in \mathbb{Z} $ be a state variable, initially $ \text{LAST\_YES} = 0 $.
Let $ Q = (q_0, q_1, \dots, q_{q-1}) $ be a sequence of $ q $ queries, each of type 1 or 2:
- Type 1: $ q_j = (1, t_j) $, where $ t_j \in \Sigma^+ $
- Type 2: $ q_j = (2, i_j, \alpha_j) $, where $ i_j \in \{0, \dots, n-1\} $, $ \alpha_j \in \{0, \dots, 25\} $
**Constraints**
1. Total length of all $ S_i $: $ \sum_{i=0}^{n-1} |S_i| \leq 200{,}000 $
2. Total length of all $ t_j $ in type-1 queries: $ \sum_{j: q_j \text{ type 1}} |t_j| \leq 200{,}000 $
3. For type-2 queries: $ 0 \leq i_j < n $, $ 0 \leq \alpha_j < 26 $
**Operations**
For each query $ j \in \{0, \dots, q-1\} $:
- **If type 1**:
Let $ d_j $ be the deciphered string:
$$
d_j[k] = \left( t_j[k] - 'a' + \text{LAST\_YES} \right) \bmod 26 + 'a', \quad \forall k \in \{0, \dots, |t_j|-1\}
$$
Output:
$$
\begin{cases}
\text{YES} & \text{if } \exists i \in \{0, \dots, n-1\} \text{ s.t. } S_i \text{ is a substring of } d_j \\
\text{NO} & \text{otherwise}
\end{cases}
$$
Update:
$$
\text{LAST\_YES} \leftarrow
\begin{cases}
j & \text{if output is YES} \\
\text{LAST\_YES} & \text{otherwise}
\end{cases}
$$
- **If type 2**:
Let $ \delta = (\alpha_j + \text{LAST\_YES}) \bmod 26 $
Let $ \ell = (i_j + \text{LAST\_YES}) \bmod n $
Update:
$$
S_\ell \leftarrow S_\ell + \left( \delta + 'a' \right)
$$
**Objective**
For each type-1 query $ j $, output the corresponding YES/NO answer as defined above.