You have a list in which you store strings. The list is indexed from 1. Initially, the list contains only one string \(S\).
There are three different types of tasks that you are asked to perform:
\(1 \quad p \quad n \quad c\): Create a new string of length \(p\) using the \(n^{th}\) string from the list such that all characters from \(1\) to \(p-1\) in the new string are the same as in the old string and the \(p^{th}\) character is \(c\). Append this string to the end of the list.
\(2 \quad p \quad n\): Create a new string of length \(p\) using the \(n^{th}\) string from the list such that all the characters from \(1\) to \(p\) in the new string are the same as in the old string. Append this string to the end of the list.
\(3 \quad l \quad r \quad s\): Print \(yes\) if string \(s\) appears as the prefix of any string in the range \([l,r]\) of the list, else print \(no\).
Input format
- First line: String \(S\) represents the only string that is initially in the list
- Next line: \(Q\) represents the number of queries to be performed
- Next \(Q\) lines: Each line describes one of the three types of tasks that can be performed. All the tasks are valid.
Output format
For every task of type \(3\), print \(yes\) or \(no\).
Constraints
\(|S| \le 10^5\)
\(Q \le 3*10^{5}\)
Constraints that apply to all the queries
For the query to perform the task of type \(1\): \(0 \le p-1 \le | size \; of \; n^{th} \; string|\)
For the query to perform the task \(2\): \(1 \le p \lt | size \; of \; n^{th} \; string|\)
\(1 \le n \le |current \; size \; of \; list|\)
\(c \in [a,b]\), i.e. all the characters are lowercase English alphabets
\(1 \le l \le r \le |current \quad size \quad of \quad list|\)
\(\sum_{Q} |s_i| \le 10^6\)
\(s_{i} \ne s_{j}\) if \(i \ne j\), for all the strings in the list. i.e. all the strings in the list are unique
\(c \in [a, z]\ (not [a, b])\)
apple 5 1 2 1 x 1 3 2 e 2 3 1 3 2 4 ap 3 1 3 aye
yes no
Initially, the list is \(['apple']\)
In first query, a task of type 1 is performed. A new string 'ax' is made and appended at end of list. The list becomes\( ['apple', 'ax']\)
In second query, again a task of type 1 is performed. This time, the new string formed is 'axe'. The list now becomes \(['apple', 'ax', 'axe']\)
In third query, a task of type 2 is performed. The new string 'app' is formed using the first 3 characters of 1st string i.e.'apple'. The list now becomes \(['apple','ax','axe','app']\)
In fourth query, since 'ap' exists as prefix of string 'app', and index of 'app' being 4, it lies in range [2,4], print yes.
In fifth query, since 'aye' doesn't exists as prefix of any string in range [1,3] of list. print no.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor