#include <stdio.h>
#include <math.h>

#define CHUNKSIZELOG 12
#define CHUNKSIZE (1<<CHUNKSIZELOG)

typedef long double ext;
typedef struct { ext r; ext i; } cmp;
typedef cmp CHUNK[CHUNKSIZE];

char quit;

ext invsqrt2;
CHUNK dtabchunk,rtabchunk,inchunk,fftchunk,newfftchunk,outchunk;

void preparefft(void)
{
  int i;
  invsqrt2 = M_SQRT1_2;
  for (i=0;i<CHUNKSIZE;i++) {
    dtabchunk[i].r = cosl(-2.0L*M_PI*((ext)i)/((ext)CHUNKSIZE));
    dtabchunk[i].i = sinl(-2.0L*M_PI*((ext)i)/((ext)CHUNKSIZE));
  }
  for (i=0;i<CHUNKSIZE;i++) {
    rtabchunk[i].r = cosl(2.0L*M_PI*((ext)i)/((ext)CHUNKSIZE));
    rtabchunk[i].i = sinl(2.0L*M_PI*((ext)i)/((ext)CHUNKSIZE));
    /* Yes, what a loss of memory... */
  }
}

void fft(int loglen,cmp *input,cmp *output,cmp *table)
{
  int i,l,l2;
  CHUNK nextinput,nextoutput;
  if (loglen==0) {
    output[0] = input[0];
    return;
  }
  if (loglen==1) {
    output[0].r = invsqrt2*(input[0].r+input[1].r);
    output[0].i = invsqrt2*(input[0].i+input[1].i);
    output[1].r = invsqrt2*(input[0].r-input[1].r);
    output[1].i = invsqrt2*(input[0].i-input[1].i);
    return;
  }
  l=(1<<loglen);
  l2=l/2;
  for (i=0;i<l2;i++) {
    nextinput[i] = input[i*2];
    nextinput[i+l2] = input[i*2+1];
  }
  fft(loglen-1,nextinput,nextoutput,table);
  fft(loglen-1,nextinput+l2,nextoutput+l2,table);
  for (i=0;i<l;i++) {
    nextoutput[i].r *= invsqrt2;
    nextoutput[i].i *= invsqrt2;
  }
  for (i=0;i<l;i++) {
    output[i].r = nextoutput[i%l2].r
                + table[i<<(CHUNKSIZELOG-loglen)].r*nextoutput[(i%l2)+l2].r
                - table[i<<(CHUNKSIZELOG-loglen)].i*nextoutput[(i%l2)+l2].i;
    output[i].i = nextoutput[i%l2].i
                + table[i<<(CHUNKSIZELOG-loglen)].i*nextoutput[(i%l2)+l2].r
                + table[i<<(CHUNKSIZELOG-loglen)].r*nextoutput[(i%l2)+l2].i;
  }
}

void directfft(void)
{
  fft(CHUNKSIZELOG,inchunk,fftchunk,dtabchunk);
}

void reversefft(void)
{
  fft(CHUNKSIZELOG,newfftchunk,outchunk,rtabchunk);
}

void processfft(void)
{
  int i;
  ext t;
  for (i=0;i<CHUNKSIZE;i++) {
    newfftchunk[i]=fftchunk[(i+CHUNKSIZE-100)%CHUNKSIZE];
  }
}

void getachunk(void)
{
  short int ichunk[CHUNKSIZE];
  int i;
  if ((i=fread(ichunk,sizeof(short int),CHUNKSIZE,stdin))<CHUNKSIZE) quit=1;
  if (i<0) i=0;
  for (;i<CHUNKSIZE;i++) {
    ichunk[i]=0;
  }
  for (i=0;i<CHUNKSIZE;i++) {
    inchunk[i].r=((ext)ichunk[i])/32767.0L;
    inchunk[i].i=0.0L;
  }
}

void processchunk(void)
{
  int i;
  fprintf(stderr,".");
  directfft();
  processfft();
  reversefft();
}

void outputchunk(void)
{
  int i;
  ext o_e;
  short int o_i;
  short int ochunk[CHUNKSIZE];
  for (i=0;i<CHUNKSIZE;i++) {
    o_e=outchunk[i].r;
    if (o_e<-1.0L) o_e=-1.0L;
    if (o_e>1.0L) o_e=1.0L;
    o_i=(short int)(o_e*32767.0L);
    ochunk[i]=o_i;
  }
  fwrite(ochunk,sizeof(short int),CHUNKSIZE,stdout);
}

void main(void)
{
  quit=0;
  preparefft();
  while (!quit) {
    getachunk();
    processchunk();
    outputchunk();
  }
  fflush(stdout);
}