import java.io.IOException; import java.io.InputStream; import java.math.BigInteger; import java.util.Arrays; import java.util.Comparator; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { new Main().run(); } long pow(long a,long n,long mod) { return n==0?1:(pow(a*a%mod,n/2,mod)*(n%2==1?a:1))%mod; } long inv(long a,long mod) { return pow(a,mod-2,mod); } final long[] MOD= {980000023,980000029,980000033}; // [l,r) long trim(int l,int r,long[] hash,long mod,boolean to_left) { int n=hash.length; if (to_left) return ((r==0?0:hash[r-1])-(l==0?0:hash[l-1])+mod)%mod*inv(pow(3,l,mod),mod)%mod; else return (hash[l]-(r==n?0:hash[r])+mod)%mod*inv(pow(3,n-r,mod),mod)%mod; } int f(int l,int r,long[][] hash0,long[][] hash1){ int n=hash0[0].length; if (l<0||r>=n||l>r) return 0; int ok=0; int ng=Math.min(l+2, (n-1-r)+2); while (ng-ok>1) { int middle=(ok+ng)/2; boolean ret=true; for (int j=0;j=0;--j) { hash1[i][j]=(j==n-1?0:hash1[i][j+1])+(int)(cs[j]-'a')*x; hash1[i][j]%=MOD[i]; x=x*3%MOD[i]; } } int even=0; int odd=0; for (int i=0;i