#include <bits/stdc++.h>
using namespace std;
struct vertex
{
static const int k=16;
int h;
map<int,vertex*> to;
vertex *up[k];
vertex():h(0){for(auto &it:up)it=this;}
bool add(char t)
{
if(to[t]) return 0;
vertex *temp=new vertex;
temp->h=this->h+1;
temp->up[0]=this;
for(int i=1;i<k;i++)
temp->up[i]=temp->up[i-1]->up[i-1];
to[t]=temp;
return 1;
}
vertex *up_to(int H)
{
H=h-H;
vertex *ret=this;
for(int i=k;i>=0;i--)
if((1<<i)<=H)ret=ret->up[i],H-=1<<i;
return ret;
}
};
template<int delta> struct base
{
private:
vector<int> rad;
string text;
int i;
int n;
vector<vertex*> link;
vertex *root;
public:
base():i(1),n(0)
{
text.push_back('$');
rad.push_back(0);
root=new vertex;
link.push_back(root);
}
bool add_letter(char t)
{
int r=0;
text+=t;
rad.push_back(0);
link.push_back(root);
int s=i;
for(; i<=n+delta; i++)
{
link[i]=link[s-(i-s)]->up_to(n-i+delta);
rad[i]=min(rad[s-(i-s)],n-i+delta);
if(text[i-rad[i]]==text[i+rad[i]+1-delta])
{
r=link[i]->add(t);
link[i]=link[i]->to[t];
rad[i]++;
break;
}
}
n++;
return r;
}
};
struct manacher
{
private:
base<0> even;
base<1> odd;
public:
int add_letter(char t)
{
return odd.add_letter(t)+even.add_letter(t);
}
} me;
main()
{
ios::sync_with_stdio(0);
cin.tie(0);
char t;
int cur(0);
while((t=getchar())!='\n')
cout<<(cur+=me.add_letter(t))<<' ';
cout<<"\n";
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IHZlcnRleAp7CiAgICBzdGF0aWMgY29uc3QgaW50IGs9MTY7CiAgICBpbnQgaDsKICAgIG1hcDxpbnQsdmVydGV4Kj4gdG87CiAgICB2ZXJ0ZXggKnVwW2tdOwoKICAgIHZlcnRleCgpOmgoMCl7Zm9yKGF1dG8gJml0OnVwKWl0PXRoaXM7fQoKICAgIGJvb2wgYWRkKGNoYXIgdCkKICAgIHsKICAgICAgICBpZih0b1t0XSkgcmV0dXJuIDA7CiAgICAgICAgdmVydGV4ICp0ZW1wPW5ldyB2ZXJ0ZXg7CiAgICAgICAgdGVtcC0+aD10aGlzLT5oKzE7CiAgICAgICAgdGVtcC0+dXBbMF09dGhpczsKICAgICAgICBmb3IoaW50IGk9MTtpPGs7aSsrKQogICAgICAgICAgICB0ZW1wLT51cFtpXT10ZW1wLT51cFtpLTFdLT51cFtpLTFdOwogICAgICAgIHRvW3RdPXRlbXA7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CgogICAgdmVydGV4ICp1cF90byhpbnQgSCkKICAgIHsKICAgICAgICBIPWgtSDsKICAgICAgICB2ZXJ0ZXggKnJldD10aGlzOwogICAgICAgIGZvcihpbnQgaT1rO2k+PTA7aS0tKQogICAgICAgICAgICBpZigoMTw8aSk8PUgpcmV0PXJldC0+dXBbaV0sSC09MTw8aTsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQp9OwoKdGVtcGxhdGU8aW50IGRlbHRhPiBzdHJ1Y3QgYmFzZQp7CnByaXZhdGU6CiAgICB2ZWN0b3I8aW50PiByYWQ7CiAgICBzdHJpbmcgdGV4dDsKICAgIGludCBpOwogICAgaW50IG47CgogICAgdmVjdG9yPHZlcnRleCo+IGxpbms7CiAgICB2ZXJ0ZXggKnJvb3Q7CgpwdWJsaWM6CgogICAgYmFzZSgpOmkoMSksbigwKQogICAgewogICAgICAgIHRleHQucHVzaF9iYWNrKCckJyk7CiAgICAgICAgcmFkLnB1c2hfYmFjaygwKTsKICAgICAgICByb290PW5ldyB2ZXJ0ZXg7CiAgICAgICAgbGluay5wdXNoX2JhY2socm9vdCk7CiAgICB9CgogICAgYm9vbCBhZGRfbGV0dGVyKGNoYXIgdCkKICAgIHsKICAgICAgICBpbnQgcj0wOwogICAgICAgIHRleHQrPXQ7CiAgICAgICAgcmFkLnB1c2hfYmFjaygwKTsKICAgICAgICBsaW5rLnB1c2hfYmFjayhyb290KTsKCiAgICAgICAgaW50IHM9aTsKICAgICAgICBmb3IoOyBpPD1uK2RlbHRhOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBsaW5rW2ldPWxpbmtbcy0oaS1zKV0tPnVwX3RvKG4taStkZWx0YSk7CiAgICAgICAgICAgIHJhZFtpXT1taW4ocmFkW3MtKGktcyldLG4taStkZWx0YSk7CgogICAgICAgICAgICBpZih0ZXh0W2ktcmFkW2ldXT09dGV4dFtpK3JhZFtpXSsxLWRlbHRhXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcj1saW5rW2ldLT5hZGQodCk7CiAgICAgICAgICAgICAgICBsaW5rW2ldPWxpbmtbaV0tPnRvW3RdOwogICAgICAgICAgICAgICAgcmFkW2ldKys7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBuKys7CiAgICAgICAgcmV0dXJuIHI7CiAgICB9Cn07CgpzdHJ1Y3QgbWFuYWNoZXIKewpwcml2YXRlOgogICAgYmFzZTwwPiBldmVuOwogICAgYmFzZTwxPiBvZGQ7CgpwdWJsaWM6CiAgICBpbnQgYWRkX2xldHRlcihjaGFyIHQpCiAgICB7CiAgICAgICAgcmV0dXJuIG9kZC5hZGRfbGV0dGVyKHQpK2V2ZW4uYWRkX2xldHRlcih0KTsKICAgIH0KfSBtZTsKCm1haW4oKQogewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgY2hhciB0OwogICAgaW50IGN1cigwKTsKICAgIHdoaWxlKCh0PWdldGNoYXIoKSkhPSdcbicpCiAgICAgICAgY291dDw8KGN1cis9bWUuYWRkX2xldHRlcih0KSk8PCcgJzsKICAgIGNvdXQ8PCJcbiI7Cn0K