K. Know Your Statement
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

The problem he came up with is the following:

Given an array v of strings, answer these queries:

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

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 the 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) and s is a string.
Output

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

Example
Input
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
Output
Y
N
Y
Y
Y
N
Y
N
Y
Note
  • 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 a prefix of string b if: .