List of Strings

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:}$

For Subtask #1 (10 points):

• $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.

For Subtask #2 (90 points):

• $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

Input	Output
5 1 aa 1 aaa 1 aaaa 2 2 2 3 1 3	2

Input	Output
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$.