{made by virt 2004}
unit dlinna;

interface
const _maxdig=1000;
      _osn=10000;

type
  Tlong=array[0 .. _maxdig]of integer;
  Plong=^Tlong;

  TObj = object
    Constructor Init;
    Destructor Done;

    procedure ReadLong(var f:text);
     procedure WriteLong(var f:text);
     procedure SumLongTwo(const a, b: TObj);
     // self <-- a + b;

     procedure SubLongTwo(const b: TObj; sdvig: integer);
     // self <-- self - b * (_osn^sdvig);

     procedure MulLongShort(const a: TObj; k: longint);
     // 0 <= k <= _osn
     // self <-- a * k;

     procedure MulLongTwo(const a, b: TObj);
     // self <-- a * b;

     procedure DivLongTwo(const a, b: TObj; var ost: TObj);
     // self <-- a div b;
     // ost  <-- a mod b;

     function EqLong(const b: TObj): boolean;
     function MoreThanLong(const b: TObj): boolean;
     function LessThanLong(const b: TObj): boolean;
     function More_EqThanLong(const b: TObj): boolean;
     function Less_EqThanLong(const b: TObj): boolean;

     function MoreSdvigLong(const a: TObj; const sdvig: integer): byte;
     // a > self*(_osn^sdvig) --> 0
     // a < self*(_osn^sdvig) --> 1
     // a = self*(_osn^sdvig) --> 2

  private
    X: PLong;
  end;

implementation

constructor TObj.Init;
begin
  new(X);
end;
destructor TObj.Done;
begin
  dispose(X);
end;


procedure TObj.ReadLong(var f:text);
var ch:char;
    i:integer;
begin
   fillchar(X^,sizeof(X^),0);
   read(f, ch);
   while not (ch in ['0'..'9',#26]) do read(f, ch);
   while ch in ['0'..'9'] do
      begin
         for i:=X^[0] downto 1 do
            begin
               X^[i+1]:=X^[i+1]+(longint(X^[i])*10)div _osn;
               X^[i]:=(longint(X^[i])*10)mod _osn;
            end;
         X^[1]:=X^[1]+ord(ch)-ord('0');
         if X^[X^[0]+1]>0 then inc(X^[0]);
         read(f,ch);
      end;
end;

procedure TObj.WriteLong(var f:text); // a:Plong);
var ls,s:string;
    i:integer;
begin
   str(_osn div 10,ls);
   write(f,X^[X^[0]]);
   for i:=X^[0]-1 downto 1 do
      begin
         str(X^[i],s);
         while length(s)<length(ls) do s:='0'+s;
         write(f,s);
      end;
   writeln(f);
end;

procedure TObj.SumLongTwo(const a,b: TObj);
var i,k:integer;
begin
   fillchar(X^,sizeof(X^),0);
   if a.X^[0] > b.X^[0] then k:=a.X^[0] else k:=b.X^[0];
   for i:=1 to k do
      begin
         X^[i+1]:=(X^[i]+a.X^[i]+b.X^[i]) div _osn;
         X^[i]:=(X^[i]+a.X^[i]+b.X^[i]) mod _osn;
      end;
   if X^[k+1]=0 then X^[0]:=k else X^[0]:=k+1;
end;

function TObj.EqLong(const b: TObj):boolean;
var i:integer;
begin
   EqLong:=false;
   if X^[0] = b.X^[0] then
      begin
         i:=1;
         while (i<=X^[0]) and (X^[i] = b.X^[i]) do inc(i);
         EqLong := (i=X^[0]+1);
      end;
end;

function TObj.MoreThanLong(const b: TObj):boolean;
var i:integer;
begin
   if X^[0]<b.X^[0] then MoreThanLong:=false else
      if X^[0]>b.X^[0] then MoreThanLong:=true else
         begin
            i:=X^[0];
            while (i>0) and (X^[i]=b.X^[i]) do dec(i);
            if i=0 then MoreThanLong:=false else
               if X^[i]>b.X^[i] then MoreThanLong:=true else MoreThanLong:=false;
         end;
end;

function TObj.LessThanLong(const b: TObj):boolean;
begin
   LessThanLong:=not(MoreThanLong(b) or EqLong(b));
end;

function TObj.More_EqThanLong(const b: TObj):boolean;
begin
   More_EqThanLong:=MoreThanLong(b) or EqLong(b);
end;

function TObj.Less_EqThanLong(const b: TObj):boolean;
begin
   Less_EqThanLong:=not(MoreThanLong(b));
end;

function TObj.MoreSdvigLong(const a: TObj; const sdvig: integer): byte;
var i:integer;
begin
   if a.X^[0]>(X^[0]+sdvig) then MoreSdvigLong:=0 else
      if a.X^[0]<(X^[0]+sdvig) then MoreSdvigLong:=1 else
         begin
            i:=a.X^[0];
            while (i>sdvig) and (a.X^[i]=X^[i-sdvig]) do dec(i);
            if i=sdvig then
               begin
                  MoreSdvigLong:=0;
                  for i:=1 to sdvig do
                     if a.X^[i]>0 then exit;
                  MoreSdvigLong:=2;
               end else
                  MoreSdvigLong:=byte(a.X^[i]<X^[i-sdvig]);{0 -- false(a>b) ;1 -- true(a<b)}
         end;
end;

procedure TObj.MulLongShort(const a: TObj; k: longint);
var i:integer;
begin
   fillchar(X^,sizeof(X^),0);
   if k=0 then inc(X^[0]) else
      begin
         for i:=1 to a.X^[0] do
            begin
               X^[i+1]:=(longint(a.X^[i])*k+X^[i]) div _osn;
               X^[i]:=(longint(a.X^[i])*k+X^[i]) mod _osn;
            end;
         if X^[a.X^[0]+1]>0 then X^[0]:=a.X^[0]+1 else X^[0]:=a.X^[0];
      end;
end;

procedure TObj.MulLongTwo(const a, b: TObj);
var i,j:integer;
    dv:longint;
begin
   fillchar(X^,sizeof(X^),0);
   for i:=1 to a.X^[0] do
      for j:=1 to b.X^[0] do
         begin
            dv:=longint(a.X^[i])*b.X^[j]+X^[i+j-1];
            X^[i+j]:=X^[i+j]+dv div _osn;
            X^[i+j-1]:=dv mod _osn;
         end;
   X^[0]:=a.X^[0]+b.X^[0];
   while (X^[0]>1) and (X^[X^[0]]=0) do dec(X^[0]);
end;

procedure TObj.SubLongTwo(const b: TObj; sdvig: integer);
var i,j:integer;
begin
   for i:=1 to b.X^[0] do
      begin
         dec(X^[i+sdvig],b.X^[i]);
         j:=i;
         while (X^[j+sdvig]<0) and (j<=X^[0]) do
            begin
               inc(X^[j+sdvig],_osn);
               dec(X^[j+sdvig+1]);
               inc(j);
            end;
      end;
   i:=X^[0];
   while (i>1) and (X^[i]=0) do dec(i);
   X^[0]:=i;
end;

function FindBin(var ost: TObj; const b: TObj; const sp: integer): longint;
var up,down:word;
    c: TObj;
begin
   c.Init;
   down:=0; up:=_osn;
   while up-1>down do
      begin
         c.MulLongShort(b,(up+down) div 2);
         case c.MoreSdvigLong(ost,sp) of
          0:down:=(up+down) div 2;
          1:up:=(up+down) div 2;
          2:begin
               up:=(up+down) div 2;
               down:=up;
            end;
         end;
      end;
   c.MulLongShort(b,(up+down) div 2);
   if c.MoreSdvigLong(ost,0)=0 then ost.SubLongTwo(c,sp) else
      begin
         c.SubLongTwo(ost,sp);
         ost:=c;
      end;
   FindBin:=(up+down) div 2;
   c.Done;
end;

procedure MakeDel(const a, b: TObj; var res, ost: TObj);
var sp:integer;
begin
   ost.X^:=a.X^;
   sp:=a.X^[0]-b.X^[0];
   if b.MoreSdvigLong(a,sp)=1 then dec(sp);{!!!!!!!!!}
   res.X^[0]:=sp+1;
   while sp>=0 do
      begin
         res.X^[sp+1]:=FindBin(ost,b,sp);
         dec(sp);
      end;
end;

procedure TObj.DivLongTwo(const a, b: TObj; var ost: TObj);
begin
   fillchar(X^,sizeof(X^),0);X^[0]:=1;
   fillchar(ost.X^,sizeof(ost.X^),0);ost.X^[0]:=1;
   case b.MoreSdvigLong(a,0) of
    0:MakeDel(a,b,self,ost);
    1:ost.X^:=a.X^;
    2:X^[1]:=1;
   end;
end;

end.