K - String operations

Time limit: 3 s
Memory limit: 2048 MiB
Languages: C, C++, Java, Python, ... (details)

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$].

For all queries, it holds that $1 \le i \le j \le n$ and $s$ is a string of lowercase English characters.

Input

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$.


Output

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

Sample test(s)

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