Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

List of Strings

By Hasinur_ · 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.


    Discussion

    Statistics


    44% Solution Ratio

    NirjhorEarliest, 4M ago

    Deshi_TouristFastest, 0.2s

    ValeraGrinenkoLightest, 27 MB

    serotoninShortest, 1461B

    Submit

    Login to submit

    Editorial

    The solution to this problem requires Trie and Binary Indexed Tree/Segment tree. Steps are given bel...

    Toph uses cookies. By continuing you agree to our Cookie Policy.