Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 200010

char str[MAXN];

struct node

{

	int tr[26];

	int len,fail;

}s[MAXN];

int ptr = 0;

int newnode(int l)

{

	int k = ptr++;

	memset(&s[k],0,sizeof(&s[k]));

	s[k].len = l;

	return k;

}

int l,r,pre,suf;

int ans1 = 0;

long long ans2 = 0;

int dep[MAXN];

void init()

{

	memset(dep,0,sizeof(dep));

	memset(str,'\0',sizeof(str));

	memset(s,0,sizeof(s));

	ans1 = ans2 = 0;

	l = 100000;r = l - 1;

	pre = suf = ptr = 0;

	newnode(0);newnode(-1);

	s[0].fail = s[1].fail = 1;

	return;

}

int getfail(int i,int p,int op)

{

	while(str[i] != str[i - op * s[p].len - op])p = s[p].fail;

	return p;

}

void extend(int i,int k,int &last,int op)

{

	int p = getfail(i,last,op);

	if(s[p].tr[k] == 0)

	{

		int np = newnode(s[p].len + 2);

		s[np].fail = s[getfail(i,s[p].fail,op)].tr[k];

		s[p].tr[k] = np;

		dep[np] = dep[s[np].fail] + 1;

		++ans1;

	}

	last = s[p].tr[k];

	ans2 += dep[last]; 

	if(s[last].len == r - l + 1)pre = suf = last;

	return;

}

char getc()

{

	register char c = getchar();

	while(!islower(c))c = getchar();

	return c;

}

int main()

{

	while(scanf("%d",&n) != EOF)

	{

		init();

		int op;

		for(int i = 1;i <= n;++i)

		{

			op = rd();

			if(op == 1)

			{

				char c = getc();

				str[--l] = c;

				extend(l,c - 'a',pre,-1);

			}

			if(op == 2)

			{

				char c = getc();

				str[++r] = c;

				extend(r,c - 'a',suf,1);

			}

			if(op == 3)printf("%d\n",ans1);

			if(op == 4)printf("%lld\n",ans2);

		}

	}

	return 0;

}