namespace FFTmatch
{
static const double PI=acos(-1);
static const double eps=0.5;
struct Complex
{
double x,y;
Complex(double X=0.0,double Y=0.0):x(X),y(Y) {}
inline friend Complex operator + (Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
inline friend Complex operator - (Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
inline friend Complex operator * (Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
template<typename T> inline friend Complex operator / (Complex a,T b) {return Complex(a.x/b,a.y/b);}
};
using VI=vector<int>;
using VC=vector<Complex>;
int rev[MAX],revnow;
inline int Sup(int N) {int K=0; while((1<<K)<N) ++K; return K;}
inline void Rea(int K) {if(K==revnow) return; rev[0]=0; for(int i=1;i<=(1<<K);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(K-1));}
inline void DFT(VC &F,int K,int typ)
{
int N=1<<K;
for(int i=0;i<N;++i) if(rev[i]>i) Swp(F[i],F[rev[i]]);
for(int len=2,l=1;len<=N;len<<=1,l<<=1)
{
Complex stp(cos(2*PI/len),sin(typ*2*PI/len));
for(int st=0;st<N;st+=len)
{
Complex omega(1,0),U,V;
for(int i=0;i<l;++i)
U=F[st+i],V=omega*F[st+i+l],
F[st+i]=U+V,F[st+i+l]=U-V,
omega=omega*stp;
}
}
if(typ==-1) for(int i=0;i<N;++i) F[i]=F[i]/N;
}
inline VI solve(char *a,char *b)
{
int n=strlen(a),m=strlen(b),N=n+m-1;
int K=Sup(N); Rea(K);
VI A,B,ans; VC F,G,H;
F.resize(1<<K),G.resize(1<<K),H.resize(1<<K);
for(int i=0;i<n;++i) A.eb(a[i]=='*'?0:a[i]-'a'+1);
for(int i=0;i<m;++i) B.eb(b[i]=='*'?0:b[i]-'a'+1);
reverse(A.begin(),A.end());
for(int i=n;i<(1<<K);++i) A.eb(0);
for(int i=m;i<(1<<K);++i) B.eb(0);
for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i]*A[i],0),G[i]=Complex(B[i],0);
DFT(F,K,1),DFT(G,K,1);
for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i],0),G[i]=Complex(B[i]*B[i]*B[i],0);
DFT(F,K,1),DFT(G,K,1);
for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i],0),G[i]=Complex(B[i]*B[i],0);
DFT(F,K,1),DFT(G,K,1);
for(int i=0;i<(1<<K);++i) H[i]=H[i]-F[i]*G[i]*Complex(2,0);
DFT(H,K,-1);
for(int i=n-1;i<m;++i) if(fabs(H[i].x)<=eps) ans.eb(i-n+2);
return ans;
}
}