404774: GYM101628 K Know Your Statement

Lucas really wanted to create an interesting problem with strings, but he spent so much time thinking that ended up with no creativity to create a better statement for this problem.

The problem he came up with is the following:

Given and array v of strings, answer these queries:

• 1. update(i, s) replace the i-th position in the array with the a string s.
• 2. vprefix(l, r, s) check whether there is any string in sub-array [l, r] which is a prefix of s.
• 3. sprefix(l, r, s) check whether s is prefix of any string in sub-array [l, r].

In the first line of input there is an integer n (1 ≤ n ≤ 10⁵) indicating the size of the array v. The following n lines display the contents of the array, where the (i + 1)-th line is the string in i-th position in the array.

In the (n + 2)-th line there is an integer q (1 ≤ q ≤ 10⁵), the number of queries to be executed. The following q lines contain the description of the q queries, one per line.

Each query is described as follows:

• Type 1: 1 i s, where i is an integer (1 ≤ i ≤ n) and s is a string.
• Type 2: 2 l r s, where l and r are integers (1 ≤ l ≤ r ≤ n) and s is a string.
• Type 3: 3 l r s, where l and r are integers (1 ≤ l ≤ r ≤ n) e s is a string.

For each query of type 2 and 3, print “Y” if the query's answer is true or “N” if it's false.

3
aaa
ab
acc
10
2 1 3 abb
2 3 3 abb
2 1 1 aaa
3 1 3 a
3 1 3 ac
3 3 3 b
3 3 3 ac
3 1 3 e
1 1 eae
3 1 3 e

Y
N
Y
Y
Y
N
Y
N
Y

• The sum of the lengths of the strings initially in the array does not exceed 5 * 10⁵
• The sum of the lengths of the strings in the queries does not exceed 5 * 10⁵
• All strings contain only lower case characters.
• String a is prefix of string b if: