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