# Victor and String

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 524288/262144 K (Java/Others)

## Description

Victor loves to play with string. He thinks a string is charming as the string is a palindromic string.

Victor wants to play $n$ times. Each time he will do one of following four operations.

Operation 1 : add a char $c$ to the beginning of the string.

Operation 2 : add a char $c$ to the end of the string.

Operation 3 : ask the number of different charming substrings.

Operation 4 : ask the number of charming substrings, the same substrings which starts in different location has to be counted.

At the beginning, Victor has an empty string.

## Input

The input contains several test cases, at most $5$ cases.

In each case, the first line has one integer $n$ means the number of operations.

The first number of next $n$ line is the integer $op$, meaning the type of operation. If $op$=$1$ or $2$, there will be a lowercase English letters followed.

$1\leq n \leq 100000$.

## Output

For each query operation(operation 3 or 4), print the correct answer.

## Sample Input

6
1 a
1 b
2 a
2 c
3
4
8
1 a
2 a
2 a
1 a
3
1 b
3
4

## Sample Output

4
5
4
5
11

hujie

## Source

BestCoder Round #52 (div.1) (\$)