There is a list $A$ of $n$ strings and $q$ queries of the following types:

- $1$ $i$ $s$: Set string at position $i$ to $s$. That is, $A[i] = s$.
- $2$ $i$ $j$ $s$: Determine whether there exists any string located in the interval [$i, j$] that is a prefix of the string $s$.
- $3$ $i$ $j$ $s$: Determine whether the string $s$ is a prefix of some string located in the interval [$i, j$].

The first line contains an integer $1 \le n \le 10^5$, the number of strings in $A$.

Then, $n$ lines follow, where the $i$-th line corresponds to the $i$-th string in $A$.

The next line contains an integer $1 \le q \le 10^5$, the number of queries to process.

Then, $q$ lines follow, each having a query in the format described above.

The sum of the lengths of the strings present in array $A$ and in all queries does not exceed $5 \cdot 10^5$.

For every query of type $2$ or $3$ answer 'YES' or 'NO' if the condition presented in the corresponding query holds or not.

Input

5
abc
a
ab
a
c
3
2 1 2 a
1 2 b
3 2 3 b

Output

YES
YES

Input

5
abc
ab
a
xy
wxz
6
2 1 2 abcdario
2 2 2 icpc
3 1 3 ab
3 1 3 x
1 2 xp
3 1 3 x

Output

YES
NO
YES
NO
YES