Can anyone solve me this coding problem? Initially you have an empty list DDD. In this problem you will be asked to execute three types of queries. The query types are described below.

111 SSS
In this query, you have to add string SSS to the list DDD

222 TTT LLL
In this query you have to remove the suffix of length LLL from the TthT^{th}Tth added string

333 iii jjj
Let,
min(Di, Dj)min(D_{i},D_{j})min(Di​,Dj​) = Lexicographically smallest among DiD_{i}Di​and DjD_{j}Dj​
max(Di, Dj)max(D_{i}, D{j})max(Di​,Dj)= Lexicographically largest among DiD_{i}Di​and DjD_{j}Dj​

In this query you have to count the number of strings DkD_{k}Dk​ such that min(Di, Dj)≤Dk≤max(Di, Dj)min(D_{i},D_{j}) \leq D_{k} \leq max(D_{i},D_{j})min(Di​,Dj​)≤Dk​≤ma x(Di​,Dj​) and 1≤k≤∣D∣1\leq k \leq |D|1≤k≤∣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 QQQ. Each of the next QQQ lines will contain one of the three types of queries as below.

111 SSS
Add SSS to your list.

222 TTT LLL
Here, 1≤T≤∣D∣1\leq T\leq |D|1≤T≤∣D∣ and 1≤L≤∣DT∣1 \leq L \leq |D_{T}|1≤L≤∣DT​∣

333 iii jjj
Here, 1≤i, j≤∣D∣1 \leq i, j \leq |D|1≤i, j≤∣D∣

Note that, there will be at least one query of type 111 and one query of type 333.

Constraints:\textbf{Constraints:}Co nstraints:

For Subtask #1 (10 points):

1≤Q≤3001 \leq Q \leq 3001≤Q≤300

1≤∣S∣≤101 \leq |S| \leq 101≤∣S∣≤10

1≤∑(∣Di∣)≤1001 \leq \sum(|D_{i}|) \leq 1001≤∑(∣Di​∣)≤100

There will be no query of type 2.

For Subtask #2 (90 points):

1≤Q≤1061 \leq Q \leq 10^{6}1≤Q≤106

1≤∣S∣≤1051 \leq |S| \leq 10^{5}1≤∣S∣≤105

1≤∑(∣Di∣)≤1061 \leq \sum(|D_{i}|) \leq 10^{6}1≤∑(∣Di​∣)≤106

Output

For query type 333, print the number of such strings in a single line.
Sample
Input Output

5
1 aa
1 aaa
1
2 2 2
3 1 3

2