void FFT(cpx P[],int n,int op)
{
  for(int i=1,j=0;i<n-1;i++)
  { 
    for(int s=n;j^=s>>=1,~j&s; );
    if (i<j) {cpx T=P[i];P[i]=P[j];P[j]=T;}
  }
  for(int d=0;(1<<d)<n;d++)
  {
    int m=(1<<d);int m2=m<<1;
    double p0=PI/m*op;
    cpx u_p(cos(p0),sin(p0));
    for(int i=0;i<n;i+=m2)
    {
      cpx u(1,0);
      FOT(j,m)
      {
        cpx &P1=P[i+j+m],&P2=P[i+j];
        cpx t=u*P1;
        P1=P2-t;P2=P2+t;u=u*u_p;
      }
    }
  }
}