Online String Modification and Substring Occurrence Queries

You are given an initial string \(init\). You need to support the following three online operations:

• Insert Operation: Append a given string to the end of the current string.
• Delete Operation: Remove a given number of characters from the end of the current string.
• Query Operation: Given a string \(s\), determine how many times \(s\) appears as a continuous (possibly overlapping) substring in the current string.

For example, if the current string is aaa and the query is to count occurrences of aa, the answer is \(2\) (since the occurrences at positions 0 and 1 overlap).

You must process the operations online, i.e. in the order given.

inputFormat

The input begins with a line containing the initial string \(init\). The second line contains an integer \(Q\), denoting the number of operations. Each of the following \(Q\) lines represents an operation in one of the following formats:

• 1 s: Append the string \(s\) to the end of the current string.
• 2 k: Delete the last \(k\) characters from the current string. It is guaranteed that \(k\) does not exceed the current string's length.
• 3 s: Output the number of times the string \(s\) appears in the current string as a continuous (possibly overlapping) substring.

outputFormat

For each query operation (operation type 3), output the corresponding count on a new line.

sample

abc
7
3 ab
1 cab
3 ab
2 3
3 ab
1 abab
3 aba

1
2
1
1