#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 300008;
int s[N];
struct node
{
    int len, fail, son[26], size;
    void init(int _len)
    {
        memset(son, 0, sizeof(son));
        fail = size = 0;
        len = _len;
    }
} tree[N];
LL num, last[2], ans, l, r;
void init()
{
    last[0] = last[1] = 0;
    ans = 0;
    num = 1;
    l = 100008, r = 100007;
    tree[0].init(0);
    memset(s, -1, sizeof(s));
    tree[1].init(-1);
    tree[0].fail = 1;
}
int getFail(int p, int d)
{
    if (d)
        while (s[r - tree[p].len - 1] != s[r])
            p = tree[p].fail;
    else
        while (s[l + tree[p].len + 1] != s[l])
            p = tree[p].fail;
    return p;
}
void Insert(int x, int d)
{
    if (d)
        s[++r] = x;
    else
        s[--l] = x;
    int father = getFail(last[d], d);
    int now = tree[father].son[x];
    if (!now)
    {
        now = ++num;
        tree[now].init(tree[father].len + 2);
        tree[now].fail = tree[getFail(tree[father].fail, d)].son[x];
        tree[now].size = tree[tree[now].fail].size + 1;
        tree[father].son[x] = now;
    }
    last[d] = now;
    if (r - l + 1 == tree[now].len)
        last[d ^ 1] = now;
    ans += tree[now].size;
}
int main()
{
    int op, n;
    while (scanf("%d", &n) != EOF)
    {
        init();
        while (n--)
        {
            char c;
            scanf("%d", &op);
            if (op == 1)
            {
                getchar();
                scanf("%c", &c);
                Insert(c - 'a', 0);
            }
            if (op == 2)
            {
                getchar();
                scanf("%c", &c);
                Insert(c - 'a', 1);
            }
            if (op == 3)
                printf("%lld\n", num - 1);
            if (op == 4)
                printf("%lld\n", ans);
        }
    }
    return 0;
}