Description

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

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

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

Operation 2 : add a char 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.

维护字符串，可以执行以下操作（初始为空串）

前端插入一个字符

后端插入一个字符

查询不同本质回文串个数

查询所有回文串个数

Format

Input

The input contains several test cases, at most cases.

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

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

Output

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

Samples

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

4
5
4
5
11