# List of Strings

Limits 1s, 512 MB

Initially you have an empty list $D$. In this problem you will be asked to execute three types of queries. The query types are described below.

• $1$ $S$
In this query, you have to add string $S$ to the list $D$

• $2$ $T$ $L$
In this query you have to remove the suffix of length $L$ from the $T^{th}$ added string

• $3$ $i$ $j$
Let,
$min(D_{i},D_{j})$ = Lexicographically smallest among $D_{i}$and $D_{j}$
$max(D_{i}, D{j})$= Lexicographically largest among $D_{i}$and $D_{j}$

In this query you have to count the number of strings $D_{k}$ such that $min(D_{i},D_{j}) \leq D_{k} \leq max(D_{i},D_{j})$ and $1\leq k \leq |D|$. Note that, we compare strings lexicographically. Lexicographical order means dictionary order.
To know more about lexicographical order, visit https://en.wikipedia.org/wiki/Lexicographic_order

All the strings will contain lowercase english alphabets only.

## Input

The first line of the input will contain a single integer $Q$. Each of the next $Q$ lines will contain one of the three types of queries as below.

• $1$ $S$
Add $S$ to your list.

• $2$ $T$ $L$
Here, $1\leq T\leq |D|$ and $1 \leq L \leq |D_{T}|$

• $3$ $i$ $j$
Here, $1 \leq i,j \leq |D|$

Note that, there will be at least one query of type $1$ and one query of type $3$.

$\textbf{Constraints:}$

• $1 \leq Q \leq 300$

• $1 \leq |S| \leq 10$

• $1 \leq \sum(|D_{i}|) \leq 100$

• There will be no query of type 2.

• $1 \leq Q \leq 10^{6}$

• $1 \leq |S| \leq 10^{5}$

• $1 \leq \sum(|D_{i}|) \leq 10^{6}$

## Output

For query type $3$, print the number of such strings in a single line.

## Samples

InputOutput
5
1 aa
1 aaa
1 aaaa
2 2 2
3 1 3

2

InputOutput
8
1 abc
1 defg
3 1 2
1 hijkl
3 2 3
2 2 1
2 2 3
3 2 3

2
2
3


After executing the $7^{th}$query, the list is $D$ $=$ [ “abc“, ““,”hijkl” ]. So, the answer to the $8^{th}$query is $3$.

### Statistics

44% Solution Ratio
NirjhorEarliest, Jun '21
nusuBotFastest, 0.2s
ValeraGrinenkoLightest, 27 MB
serotoninShortest, 1461B