#include<bits/stdc++.h>
using namespace std;
class Automaton
{
    public:
    static const int maxn=100005,ALP=26;
    int last,next[maxn*2][ALP],p,fail[maxn*2],len[maxn*2];
    long long sum;
    virtual void init();
    virtual int newnode(int l);
    virtual void add(int c);
};
class SuffixAutomaton:Automaton
{
    void init()
    {
        sum=last=p=0,fail[0]=-1;
        newnode(0);
    }
    int newnode(int l)
    {
        for(int i=0;i<ALP;i++)next[p][i]=-1;
        len[p]=l;
        return p++;
    }
    void add(int c)
    {
        int cur=newnode(len[last]+1),t=last;
        for(;t!=-1&&next[t][c]==-1;t=fail[t])next[t][c]=cur;
        if(t==-1)fail[cur]=0;
        else
        {
            int q=next[t][c];
            if(len[t]+1==len[q])fail[cur]=q;
            else
            {
                int clone=newnode(len[t]+1);
                fail[clone]=fail[q];
                for(int i=0;i<26;i++)next[clone][i]=next[q][i];
                for(;t!=-1&&next[t][c]==q;t=fail[t])next[t][c]=clone;
                fail[q]=fail[cur]=clone;
            }
            
        }
        last=cur;
        sum+=len[cur]-len[fail[cur]];
    }
}sam;
class PalindromeAutomaton:Automaton
{
    int s[maxn],n;
    int cnt[maxn];//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
    int num[maxn];//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数
    //num[last]为最后添加的一个字母所增加的回文子串个数。
    int newnode(int l)
    {
        for(int i=0;i<ALP;i++)next[p][i]=0;
        cnt[p]=num[p]=0,len[p]=l;
        return p++;
    }
    void init()
    {
        sum=p=last=n=0,s[n]=-1,fail[0]=1;
        newnode(0),newnode(-1);
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])x=fail[x];
        return x;
    }
    void add(int c)
    {
        s[++n]=c;
        int cur=get_fail(last);
        if(!next[cur][c])
        {
            int now=newnode(len[cur]+2);
            fail[now]=next[get_fail(fail[cur])][c];
            next[cur][c]=now,num[now]=num[fail[now]] + 1;
        }
        last=next[cur][c];
        cnt[last]++;
    }
    void count()
    {
        for(int i=p-1;i>=0;i--)cnt[fail[i]]+=cnt[i];
    }
}pam;
int main()
{

    return 0;
}