Dynamic String Editor

You are given an initially empty string S. You have to perform Q operations on S. There are three types of operations:

1. 0: Insert a string \(y_i\) at position \(x_i\). This means update \(S = S[0:x_i] + y_i + S[x_i:]\).
2. 1: Delete the substring in the range \([x_i, y_i)\) (i.e. remove characters from index \(x_i\) to \(y_i-1\)).
3. 2: Query the substring of S defined by \([x_i, y_i)\) and count how many times a given substring \(z_i\) appears (counting overlapping occurrences).

For every operation of type 2, output the result in the order in which the queries occur.

inputFormat

The first line contains an integer \(Q\), representing the number of operations.

Each of the next \(Q\) lines contains an operation in one of the following formats:

• 0 x y: Insert the string y at position x.
• 1 x y: Delete the substring from index x to y-1 (i.e. the range \([x, y)\)).
• 2 x y z: Query the substring from index x to y-1 and count the number of occurrences of substring z within it (overlapping allowed).

All indices are 0-based.

outputFormat

For each operation of type 2, output a single integer on a new line representing the count of occurrences of the given substring in the specified substring of S.

sample

7
0 0 abc
0 3 def
2 0 6 abc
1 2 4
2 0 4 b
0 2 xy
2 0 6 y

1
1
1