Online String Editor and Substring Query

You are given an initial string init. You need to support two types of operations online:

• Append Operation: Append a given string to the end of the current string.
• Query Operation: Given a string s, count the number of times s appears in the current string as a contiguous substring.

Formally, if the current string is S and a query string is p, you need to compute the value

$$\text{count} = \sum_{i=1}^{|S|-|p|+1} 1_{\{S[i:i+|p|-1]=p\}}.$$

The operations are performed online, i.e. each query or append operation should be processed in order.

inputFormat

The first line contains the initial string init.

The second line contains an integer Q representing the number of operations.

The following Q lines each describe an operation. Each operation is in one of the following formats:

• 1 x — Append the string x to the current string.
• 2 x — Query how many times the string x appears as a contiguous substring in the current string.

outputFormat

For each query operation (operation type 2), output a line containing a single integer which is the count of occurrences of the query string in the current string.

sample

ab
3
2 a
1 cc
2 ab

1
1