COT4 - Count on a trie

Maintain two sets of strings S and T. Initially, each set contains an empty string with id 1.

Your program are to perform the following four operations:

  1. Add a char c to the end of an existed string Si in S, then insert the new string into S. Since there has been n strings in S already, the new string will hold the id n+1.
  2. Add a char c to the beginning or to the end of an existed string Ti in T, then insert the new string into T.
  3. Choose two existed strings Ti and Tj from T, next combine them into a new one TiTj, then insert the new string into T.
  4. Print the time that an existed string Ti in T appears in an string Si in S. Your program should print 0 if Ti is an empty string.

Input

In the first line, there is an integer Q, which means the number of operations to perform.

In the next Q lines,the i-th line describes the i-th operation containing some integers. Such a line may look like this:

  • 1 Si c
  • 2 0 Ti c => add c to the beginning of Ti
  • 2 1 Ti c => add c to the end of Ti
  • 3 Ti Tj
  • 4 Ti Si

Q <= 300000, 'a' <= c <= 'z'

The number of the first operation will not exceed 100000. 

The number of the third operation will not exceed 30000.

The number of fourth operation will not exceed 100000.

Output

For each "4 Ti Si" operation, print its result.

Example

Input:
18
1 1 a
1 2 a
1 3 b
1 2 b
1 5 a
1 5 b
2 1 1 a
3 2 2
2 0 3 b
2 1 2 b
3 2 5
3 5 2
4 7 6
4 5 6
4 3 4
4 2 4
4 2 7
4 2 6

Output:
1
1
1
2
1
2

Added by:Fotile
Date:2012-05-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2020-04-17 11:10:14 [Rampage] Blue.Mary
The 4th operation actually means "The number of consecutive substrings of Si which equals to Ti"
2018-06-13 18:15:03
What is the meaning of the sentence "Print the time that an existed string Ti in T appears...."??
2012-05-25 03:07:49 Tom Chen
It's said that the S is labeled from 1,But there're 0s exist in test data.

--The testdata has been modified. Thx

Last edit: 2012-05-29 02:05:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.