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