描述

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.

格式

输入格式

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.

输出格式

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

样例1

样例输入1

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

样例输出1

1
1
1
2
1
2

限制