Victor喜欢与字符串玩耍。 当且仅当某个字符串是回文串的时候，他认为这个字符串是优美的。 Victor一共要进行$n$次操作，操作一共有四种： 操作一：在当前字符串的最前端增加一个字符$c$。 操作二：在当前字符串的最末端增加一个字符$c$。 操作三：查询当前字符串中有多少不一样的子串是优美串。 操作四：查询当前字符串中有多少子串是优美串（相同的串需要重复计算）。 每次开始玩之前，Victor都会拥有一个空字符串。
有多组测试数据（最多五组）。 每组测试数据的第一行有一个整数$n$，表示Victor的操作次数。 之后一共有$n$行，每行的开头有一个整数$op$，表示操作的类型，当$op$=$1$或$2$时，后面会跟着一个小写字母$c$。 $1\leq n\leq 100000$。
对于每个查询操作（操作三或四），输出相应的答案。
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