Given a string s , process q queries, each having one of the following forms: 1 i c — Change the i -th character in the string to c . 2 l r y — Consider the substring of s starting at position l and ending at position r . Output the number of times y occurs as a substring in it. The first line of the input contains the string s ( 1 ≤ | s | ≤ 10 5 ) of lowercase English letters. The second line contains an integer q ( 1 ≤ q ≤ 10 5 ) — the number of queries to process. The next q lines describe the queries and may have one of the following forms: 1 i c ( 1 ≤ i ≤ | s | ) 2 l r y ( 1 ≤ l ≤ r ≤ | s | ) c is a lowercase English letter and y is a non-empty string consisting of only lowercase English letters. The sum of | y | over all queries of second type is at most 10 5 . It is guaranteed that there is at least one query of second type. All strings are 1 -indexed. | s | is the length of the string s . For each query of type 2 , output the required answer in a separate line. Consider the first sample case. Initially, the string aba occurs 3 times in the range 1, 7 . Note that two occurrences may overlap. After the update, the string becomes ababcbaba and now aba occurs only once in the range 1, 7 .