List of Strings

Hasinur_ Replay of National High S...
Limits 1s, 512 MB

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

  • 11 SS
    In this query, you have to add string SS to the list DD

  • 22 TT LL
    In this query you have to remove the suffix of length LL from the TthT^{th} added string

  • 33 ii jj
    Let,
    min(Di,Dj)min(D_{i},D_{j}) = Lexicographically smallest among DiD_{i}and DjD_{j}
    max(Di,Dj)max(D_{i}, D{j})= Lexicographically largest among DiD_{i}and DjD_{j}

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

  • 11 SS
    Add SS to your list.

  • 22 TT LL
    Here, 1TD1\leq T\leq |D| and 1LDT1 \leq L \leq |D_{T}|

  • 33 ii jj
    Here, 1i,jD1 \leq i,j \leq |D|

    Note that, there will be at least one query of type 11 and one query of type 33.

Constraints:\textbf{Constraints:}

For Subtask #1 (10 points):

  • 1Q3001 \leq Q \leq 300

  • 1S101 \leq |S| \leq 10

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

  • There will be no query of type 2.

For Subtask #2 (90 points):

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

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

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

Output

For query type 33, 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 7th7^{th}query, the list is DD == [ “abc“, ““,”hijkl” ]. So, the answer to the 8th8^{th}query is 33.


Submit

Login to submit.

Statistics

40% Solution Ratio
NirjhorEarliest, Jun '21
Deshi_TouristFastest, 0.2s
ValeraGrinenkoLightest, 27 MB
serotoninShortest, 1461B
Toph uses cookies. By continuing you agree to our Cookie Policy.