SP11482 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.

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**

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