{$N+,E+}
Program FFTmul;
Const Base=1000;  LBase=3;  invBase=1/Base;
      Pi=3.14159265358979324;
type complex=record
               ip,rp:Extended;
             end;
Var i, j, len, n, n2 :LongInt;
    a, b, c, d :Array[0..511] of Complex;
    st, tmpI, tmpR :Extended;

Procedure print(x:Array of Complex; n:LongInt);
 var i :LongInt;
 Begin
   For i:=0 to n-1 do write(x[i].rp:9:1,'+',x[i].ip:8:1,'i',' ');
   writeln;
 End;

procedure FFT(x:array of complex; Var y:array of complex; st:Extended; n,n2,sign:Longint);
 Var i, j :LongInt;  tmp,tmpI,tmpR :Extended;
 Begin
   for i:=0 to n2-1 do begin
     tmpR:=0;
     tmpI:=0;
     for j:=0 to n2-1 do begin
       tmp:=sign*i*j*st;
       tmpR:=tmpR + x[j].rp*cos(tmp) - x[j].ip*sin(tmp);
       tmpI:=tmpI + x[j].rp*sin(tmp) + x[j].ip*cos(tmp);
      end;
     y[i].rp:=tmpR;
     y[i].ip:=tmpI;
    end;
 End;

Begin
  Randomize;

  assign(input ,'D:\mul.in');
  assign(output,'D:\mul2.out');
  reset(input);
  rewrite(output);

  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  fillchar(c,sizeof(c),0);
  fillchar(d,sizeof(d),0);

  Readln(len);
  For i:=0 to len do read(a[i].rp);
    {a[i].rp:=trunc(random*Base);}
  readln;
  For i:=0 to len do read(b[i].rp);
    {b[i].rp:=trunc(random*Base);}
  n:=1;

  while n<len do n:=n shl 1;
  n2:=n+n;

  Writeln('n2=',n2,' n=',n);
  st:=Pi/n;
  Writeln('a,b=');
  print(a,n2);
  print(b,n2);

  FFT(a,c,st,n,n2,1);
  FFT(b,d,st,n,n2,1);

  Writeln('c,d (After FFT)=');

  print(c,n2);
  print(d,n2);

  For i:=0 to n2-1 do begin
    tmpR:=c[i].rp * d[i].rp - c[i].ip * d[i].ip;
    tmpI:=c[i].rp * d[i].ip + c[i].ip * d[i].rp;
    c[i].rp:=tmpR;
    c[i].ip:=tmpI;
   end;

  writeln('c (After Mul)=');
  print(c,n2);

  FFT(c,d,st,n,n2,-1);

  Writeln('d (After invFFT)=');
  print(d,n2);

  for i:=0 to n2-1 do Begin
    d[i].rp:=Round(d[i].rp / n2);
    d[i].ip:=d[i].ip / n2;
   End;

  Writeln('d(After Div)=');
  print(d,n2);

  close(input);
  close(output);
End.