You are given Q queries and a string S of length N.
The queries are of the following three types:
Input format
Output format
Print the answer for each query of type 2 and 3.
Constraints
1≤N≤1000001≤x,y≤current length of string1≤p≤current length of stringl+p−1≤r≤current length of stringa<c<z1≤Q≤200000
Note: S contains only lowercase English alphabets.
For query 1, the suffix of length 1 ending at index 3 and 5 is the maximum length of the prefix that matches.
For query 3, only one substring matches with S[5, 6] matches with S[1, 2].