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(); } final long[] MOD= {980000023,980000029,980000033}; long[][] ip3=new long[3][(int)3e5]; { ip3[0][0]=ip3[1][0]=ip3[2][0]=1; for (int i=0;i=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