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])\)