404774: GYM101628 K Know Your Statement
Description
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 ≤ 105) 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 ≤ 105), 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.
ExampleInput3Output
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
YNote
N
Y
Y
Y
N
Y
N
Y
- The sum of the lengths of the strings initially in the array does not exceed 5 * 105
- The sum of the lengths of the strings in the queries does not exceed 5 * 105
- All strings contain only lower case characters.
- String a is prefix of string b if: