|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
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$].
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