#include using namespace std; #define PB push_back #define ZERO (1e-10) #define INF int(1e9+1) #define CL(A,I) (memset(A,I,sizeof(A))) #define DEB printf("DEB!\n"); #define D(X) cout<<" "<<#X": "<B&&A-ZERO pll; typedef vector vi; typedef pair ii; typedef vector vii; #define IN(n) int n;scanf("%d",&n); #define FOR(i, m, n) for (int i(m); i < n; i++) #define F(n) FOR(i,0,n) #define FF(n) FOR(j,0,n) #define FT(m, n) FOR(k, m, n) #define aa first #define bb second void ga(int N,int *A){F(N)scanf("%d",A+i);} #define MX (333333) ll pw(ll n,ll k,ll MOD){ ll r(1); while(k){ if(k&1)r*=n,r%=MOD; n*=n,n%=MOD,k>>=1; } return r; } ll inv(ll a,ll MOD){return pw(a,MOD-2,MOD);} struct HSH{ int MOD,N,I[MX],F[MX],P; void ini(char*r,int M=1000000007,ll b=257){ MOD=M,N=strlen(r),P=1,*I=1,I[1]=inv(b,MOD),*F=*r; FT(2,N)I[k]=I[k-1]*ll(I[1])%MOD; FT(1,N)P=P*b%MOD,F[k]=(ll(P)*r[k]+F[k-1])%MOD; } ll get(int b,int e){return (F[e]-ll(b?F[b-1]:0)+MOD)*I[b]%MOD;} }X,Y; unordered_set T[MX]; int N,Q,B[MX],a; char s[MX],r[MX]; int go(){ int S=0,l=-1,T=0; F(N){ l=max(l,i+B[i]-1); if(i==T){ if(l