/// manachar
int pal[N];
char s[N];
void manach(char *str){
    int i, now = 0;
    for(i = 0; str[i]!='\0'; i++){
        s[2*i] = str[i];
        s[2*i + 1] = '#';
    }
    s[2*i-1] = '\0';
    pal[0] = 0;
    for(i = 1; s[i]!='\0'; i++){
        pal[i] = max(0,min(pal[now]-(i-now),pal[now-(i-now)])) + 1;
        while(i-pal[i]>=0 && s[i+pal[i]]==s[i-pal[i]]) pal[i]++;
        pal[i]--;
        if(i+pal[i]>now+pal[now]) now = i;
    }
    for(i = 0; s[i]!='\0'; i++){
        if(s[i]=='#') pal[i] = (pal[i]+1)/2;
        else pal[i] = pal[i]/2;
    }
}