#define __complex__ _Complex
#include <stdio.h>
#include <math.h>
#include <complex.h>
typedef _Complex float c;
typedef _Complex double d;
void pc(c a){printf("%14.7e + %14.7ei\n", creal(a), cimag(a));}

void fft(const int n, c a[n]){
  int j=0; for(int i=0; i<n-1; ++i) {
    if(i<j) {c t=a[j]; a[j]=a[i]; a[i]=t;}
    {int m=n/2; while(m<=j) {j -= m; m /= 2;} j += m;}} 
  {int j=1; d b=-1; while(j<n) {d w = 1;
    for(int m=0; m<j; ++m) {
      for(int i=m; i<n; i+=j+j)
        {c t = w*a[i+j]; a[i+j]=a[i]-t; a[i] += t;}
      w *= b;}
    j *= 2; b = csqrt(b);}}}