{$N+}
{D-,E+,F-,G+,I-,L-,P+,X+,Y-}
{Q-,R-,S-,T-,V-}
{M 65520,0,655360}
Program FFTMul;
Uses dos;
Const MaxSize=1 shl 4; pi=3.141592653589793238; Bas=100000; LBas=5; invBas=1/Bas;
type complex=record
         i,r:Extended;
        end;
Var i, j, k, n, asize, bSize :Longint;
    WorstEr{, MaxNum }:Extended;
    aCoef, bCoef, ccoef :Array[0..Pred(MaxSize)] of LongInt;
    Time1,Time2,th2,tm2,ts2,tms2,th1,tm1,ts1,tms1:Word;

Procedure Initial(Var w:Array of Complex; Var lst:Array of word; n:LongInt);
 Var i, j, n2, m :LongInt;
     tmp :Extended;
 Begin
   i:=0;
   tmp:=2*pi/n;
   n2:=n shr 2;
   For i:=0 to n2 do Begin
     w[i].i:=sin(tmp*i);
     w[i].r:=Sqrt(1-sqr(w[i].i));
   End;
   i:=Pred(n2);   j:=succ(n2);
   While i>=0 do Begin
     w[j].i:= w[i].i;
     w[j].r:=-w[i].r;
     Dec(i);  Inc(j);
   End;
   n2:=n;  lst[0]:=0;  m:=1;   i:=1;
   While n2<>1 do Begin
     n2:=n2 shr 1;
     m :=m  shl 1;
     j:=0;
     While i<m do Begin
       lst[i]:=lst[j]+n2;
       inc(i);  inc(j);
     End;
   End;
 End;

Procedure PZero(x:LongInt);
 Begin
   Inc(x);
   While x<(Bas*0.1) do Begin
     Write('0');
     x:=x*10;
    End;
 End;

Procedure Print(a:Array of LongInt; n:LongInt);
 Var i :LongInt;
 Begin
   Write (a[0]);
   For i:=1 to pred(n) do begin
     PZero (a[i]);
     Write (a[i]);
   end;
 End;

Procedure FFT(Const a:Array of Complex; Var b:Array of Complex;Const w:Array of Complex;Const lst:Array of Word; n:Longint);
 Var per, m, n2, n1, j, k, i2, p :LongInt;
     tmp1, tmp2 :Extended;
     Tmpb, Tmpb2 :Complex;
 Begin
   For j:=0 to pred(n) do  b[j]:=a[lst[j]];
   n2:=1;  per:=1;
   n1:=n shr 1;
   While per<n do Begin
     m:=n2;  j:=0;  k:=n2;
     per:=per shl 1;
     While k<n do Begin
       i2:=0;
       While j<m do Begin
         Tmpb:=b[j];
         Tmp1:=b[k].r*w[i2].r-b[k].i*w[i2].i;
         Tmp2:=b[k].r*w[i2].i+b[k].i*w[i2].r;
         b[j].r:=Tmpb.r+Tmp1;
         b[j].i:=Tmpb.i+Tmp2;
         b[k].r:=Tmpb.r-Tmp1;
         b[k].i:=Tmpb.i-Tmp2;
         Inc(j);   Inc(k);   Inc(i2,n1);
       End;
       Inc(m, per);  Inc(j, n2);  Inc(k, n2);
     End;
     n2:=per;
     n1:=n1 shr 1;
   End;
 End;

Procedure invFFT(Const a:Array of Complex; Var b:Array of Complex;Const w:Array of Complex;Const lst:Array of Word; n:Longint);
 Var per, m, n1, n2, j, k, i2 :LongInt;
     Tmp1, Tmp2 :Extended;
     Tmpb :Complex;
 Begin
   For j:=0 to pred(n) do  b[j]:=a[lst[j]];
   n2:=1;  per:=1;
   n1:=n shr 1;
   While per<n do Begin
     m:=n2;  j:=0;  k:=n2;
     per:=per shl 1;
     While k<n do Begin
       i2:=0;
       While j<m do Begin
         Tmpb:=b[j];
         Tmp1:=b[k].r*w[i2].r+b[k].i*w[i2].i;
         Tmp2:=b[k].r*w[i2].i-b[k].i*w[i2].r;
         b[j].r:=Tmpb.r+Tmp1;
         b[j].i:=Tmpb.i-Tmp2;
         b[k].r:=Tmpb.r-Tmp1;
         b[k].i:=Tmpb.i+Tmp2;
         Inc(j);  Inc(k);  Inc(i2,n1);
       End;
       Inc(m, per);  Inc(j, n2);  Inc(k, n2);
     End;
     n2:=per;
     n1:=n1 shr 1;
   End;
   Tmp1:=1/n;
   For j:=0 to pred(n) do
     b[j].r:=b[j].r*Tmp1;
 End;

Procedure MulFFT(Const ACoef:Array of LongInt; ASize:LongInt;Const BCoef:Array of LongInt; BSize:LongInt;
                   Var CCoef:Array of LongInt);
 Var a, b, tmp :Array[0..MaxSize] of complex;
     lst :Array[0..pred(MaxSize)] of Word;
     w   :Array[0..MaxSize shr 1] of complex;
     n, i :LongInt;
     logn :Byte;
     TmpR, num{,maxr,maxi }:Extended;
 Begin
   n:=1;
   logn:=0;
   while n<(aSize+bSize) do Begin n:=n shl 1; Inc(logn); End;
   Initial(w,lst,n);
   for i:=0 to ASize do Begin
     a[i].r:=ACoef[i];
     a[i].i:=0;
   End;
   for i:=asize to n do Begin
     a[i].r:=0;   a[i].i:=0;
   End;
   for i:=0 to BSize do Begin
     b[i].r:=BCoef[i];
     b[i].i:=0;
   End;
   for i:=bsize to n do Begin
     b[i].r:=0;   b[i].i:=0;
   End;
{   maxr:=0;
   maxi:=0;}
   FFT(a, b, w, lst, n);
   FFT(b, tmp, w,lst, n);
   For i:=0 to pred(n) do Begin
     a[i].r:=tmp[i].r*b[i].r - tmp[i].i*b[i].i;
     a[i].i:=tmp[i].r*b[i].i + tmp[i].i*b[i].r;
   End;
   invFFT(a, b, w, lst, n);
{   For i:=0 to pred(n) do if Abs(b[i].r)>Maxr then maxr:=Abs(b[i].r);
   For i:=0 to pred(n) do if Abs(b[i].i)>Maxi then maxi:=Abs(b[i].i);}
   TmpR:=0;
   For i:=pred(n) downto 1 do Begin
     num:=b[pred(i)].r+TmpR;
     TmpR:=Int((num+0.1)*invBas);
     CCoef[i]:=Round(num-TmpR*Bas);
     If ABS(num-TmpR*Bas-CCoef[i]) > WorstEr Then WorstEr:=Abs((num-TmpR*Bas)-CCoef[i]);
   End;
   CCoef[0]:=Round(TmpR);
 End;

Procedure SquareFFT(Const ACoef:Array of LongInt; ASize:LongInt; Var CCoef:Array of LongInt);
 Var a, b :Array[0..MaxSize] of complex;
     lst :Array[0..pred(MaxSize)] of Word;
     w   :Array[0..MaxSize shr 1] of complex;
     n, i :LongInt;
     logn :Byte;
     TmpR, num{,maxr,maxi }:Extended;
 Begin
   n:=1;
   logn:=0;
   while n<(aSize+aSize) do Begin n:=n shl 1; Inc(logn); End;
   Initial(w,lst,n);
   for i:=0 to Pred(ASize) do Begin
     a[i].r:=ACoef[i];
     a[i].i:=0;
   End;
   for i:=asize to n do Begin
     a[i].r:=0;  a[i].i:=0;
   End;
{   maxr:=0;
   maxi:=0;}
   FFT(a, b, w, lst, n);
   For i:=0 to pred(n) do Begin
     a[i].r:=b[i].r*b[i].r - b[i].i*b[i].i;
     a[i].i:=b[i].r*b[i].i + b[i].i*b[i].r;
   End;
   invFFT(a, b, w, lst, n);
{   For i:=0 to pred(n) do if Abs(b[i].r)>Maxr then maxr:=Abs(b[i].r);
   For i:=0 to pred(n) do if Abs(b[i].i)>Maxi then maxi:=Abs(b[i].i);}
   TmpR:=0;
   For i:=Pred(n) downto 1 do Begin
     num :=b[Pred(i)].r+TmpR;
     TmpR:=Int((num+0.001)*invBas);
     CCoef[i]:=Round(num-TmpR*Bas);
     If ABS(num-TmpR*Bas-CCoef[i]) > WorstEr Then WorstEr:=Abs((num-TmpR*Bas)-CCoef[i]);
   End;
   CCoef[0]:=Round(TmpR);
 End;

Begin
  Assign(output,'D:\Mulout.txt');
  Rewrite(output);
  Randomize;
  WorstEr:=0;
  fillchar(ACoef,sizeof(ACoef),0);
  fillchar(BCoef,sizeof(BCoef),0);
  asize:=Maxsize shr 1;
  BSize:=Maxsize shr 1;
  For i:=0 to pred(Asize) do
    ACoef[i]:={Round(Bas-1)}Trunc(random*Bas);
  Print(ACoef, Asize); Writeln; writeln('*');
  For i:=0 to pred(Bsize) do
    BCoef[i]:={Round(Bas-1)}Trunc(random*Bas);
  Print(BCoef, BSize); Writeln; Writeln('=');

 Gettime(th1,tm1,ts1,tms1);
   SquareFFT(ACoef,ASize,CCoef);{MulFFT(ACoef, ASize, BCoef, BSize, CCoef);}
 Gettime(th2,tm2,ts2,tms2);

  Print(CCoef, Asize+BSize); Writeln;
  Writeln('Worst Error is ',WorstEr);
  time1:=60*(tm2-tm1)+ts2-ts1;
  If tms2<tms1 then Begin time2:=100+tms2-tms1; Dec(time1); End
                    else time2:=tms2-tms1;
  Writeln('Used ',time1:4,'.',time2:2,'  second');
  Close(output);
End.