#include <stdio.h>
static void v(int j){if(j<0 || j>= 1024) printf("Fail!\n");}

void fft(const int n){
  {int j=0, i; for(i=0; i<n-1; ++i) {
    if(i<j) {v(i); v(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, m;/*c b=-1;*/ while(j<n) { // c w = 1;
    for(m=0; m<j; ++m) {int i;
      for(i=m; i<n; i+=j+j) {v(i+j); v(i);}
        // {c t = w*a[i+j]; a[i+j]=a[i]-t; a[i] += t;}
      /*w *= b;*/}
    j *= 2; /*b = Sqrt(b);*/}}}

int main(){fft(1024);}