program atminties_paskirstymas;

  uses atmintis;

  const MAX_BL = 1024; { maksimalus blok— skai‡ius }
  type blokas = record
                   bloko_dydis: longint;
                   rasymo_op_nr: longint;
                 end;
       atmint = array [1..MAX_BL] of blokas;


   { ‘emiau apra˛yti globalieji kintamieji }
   var N,                         { atminties dydis yra 2^N }
       bloku_kiekis: longint;     { atminties blok— kiekis }
       atm: atmint;               { atmintis }

  procedure sujungti (blk_nr: longint);
    { sujungiami du blokai }
    var i: integer;
  begin
    jungti (blk_nr);
    atm[blk_nr].bloko_dydis := atm[blk_nr].bloko_dydis + 1;
    for i := blk_nr+1 to bloku_kiekis-1 do
      begin
        atm[i].bloko_dydis  := atm[i+1].bloko_dydis;
        atm[i].rasymo_op_nr := atm[i+1].rasymo_op_nr;
      end;
    atm[bloku_kiekis].bloko_dydis  := 0;
    atm[bloku_kiekis].rasymo_op_nr := 0;
    bloku_kiekis := bloku_kiekis - 1;
  end; { sujungti }

  procedure  dalinti_pusiau (blk_nr: longint);
    { nurodytasis blokas padalinamas pusiau }
    var i: integer;
  begin
    pusiau (blk_nr);
    atm[blk_nr].bloko_dydis := atm[blk_nr].bloko_dydis - 1;
    { pernumeruojami tolesni blokai }
    for i := bloku_kiekis downto blk_nr + 1 do
      begin
        atm[i+1].bloko_dydis  := atm[i].bloko_dydis;
        atm[i+1].rasymo_op_nr := atm[i].rasymo_op_nr;
      end;
    atm[blk_nr+1].bloko_dydis  := atm[blk_nr].bloko_dydis;
    atm[blk_nr+1].rasymo_op_nr := atm[blk_nr].rasymo_op_nr;
    bloku_kiekis := bloku_kiekis + 1;
  end; { dalinti_pusiau }

  procedure sudaryti_bloka (blk_nr, blk_dydis: longint);
    { sudaro blok…, kurio dydis 2^blk_nr, pradedant nurodytu bloku }
  begin
    if atm[blk_nr].bloko_dydis > blk_dydis { jei blokas per didelis }
       then while atm[blk_nr].bloko_dydis <> blk_dydis do
                   dalinti_pusiau (blk_nr)
   else if atm[blk_nr].bloko_dydis < blk_dydis { jei ma‘esnis nei reikia }
       then begin { sudarome du blokus }
              if (atm[blk_nr].bloko_dydis <> blk_dydis - 1) or
                 (atm[blk_nr+1].bloko_dydis <> blk_dydis - 1)
                 then begin
                        sudaryti_bloka (blk_nr, blk_dydis-1);
                        sudaryti_bloka (blk_nr+1, blk_dydis-1);
                      end;
                 sujungti (blk_nr);
           end;
  end; { sudaryti_blok… }

  function dv_laipsn (lp: longint): longint;
    { apskai‡iuoja dvejeto laipsn¨ }
    var rez, i: longint;
  begin
    rez := 1;
    for i := 1 to lp do
      rez := rez * 2;
    dv_laipsn := rez;
  end; { dv_laipsn }

  function log_2 (x: longint): longint;
    var y: longint;
  begin
    y := -1;
    while x > 0 do
      begin
        x := x div 2;
        y := y + 1;
      end;
    log_2 := y;
  end; { log_2 }

  function rasti_laisva_bloka (b: longint): longint;
     { suranda laisv… blok…, ¨ kur¨ tilpt— b bait—; jei tokio
       bloko nepavyksta rasti, funkcijos reik˛m‚ prilyginama nuliui }
     var laips, i, blk_nr, maz, max_dydis, nuo, bl_dydis: longint;
  begin
    { apskai‡iuojame reikalingo bloko dyd¨ }
    bl_dydis := 0;
    laips := 1;
    while b > laips do
      begin
        laips := laips * 2;
        bl_dydis := bl_dydis + 1;
      end;
    { randame ma‘iausi… blok… ¨ kur¨ tilpt— m–s— duomenys }
    blk_nr := 0;  maz := N;
    i := 1;
    nuo := 1; { nuo ˛io bloko prasideda tu˛‡i— blok— eil‚ }
    max_dydis := 0;
    while i <= bloku_kiekis do
      begin
        if atm[i].rasymo_op_nr = 0 { jei tai tu˛‡ias blokas }
           then begin
                  max_dydis := max_dydis + dv_laipsn (atm[i].bloko_dydis);
                end;
        if (atm[i].rasymo_op_nr <> 0) or
           (atm[i].rasymo_op_nr = 0) and (i = bloku_kiekis)
           then begin { jei prasideda u‘pildytas blokas }
                  if (log_2(max_dydis) >= bl_dydis) and
                     (log_2(max_dydis) <= maz)
                     then begin
                            maz := log_2(max_dydis);
                            blk_nr := nuo;
                          end;
                  max_dydis := 0;
                  nuo := i + 1;
                end;
        i := i + 1
      end;
    if blk_nr <> 0 { jei galime sudaryti reikiamo dyd‘io blok… }
       then if atm[blk_nr].bloko_dydis > bl_dydis
               { jei turimas blokas per didelis }
               then while atm[blk_nr].bloko_dydis > bl_dydis do
                       dalinti_pusiau (blk_nr)
               else sudaryti_bloka (blk_nr, bl_dydis);
    rasti_laisva_bloka := blk_nr;
  end; { rasti_laisv…_blok… }

  procedure irasyti (nr, ba: longint; var ivykdyta: boolean);
    { ¨vykdo ¨ra˛ymo komand… }
    var bloko_numeris: longint;
  begin
    bloko_numeris := rasti_laisva_bloka (ba);
    ivykdyta := bloko_numeris <> 0;
    if ivykdyta then begin
                       rasyti (bloko_numeris, ba);
                       atm[bloko_numeris].rasymo_op_nr := nr;
                     end;
  end; { ira˛yti }

  var op: char;         { vykdoma operacija }
      nr, b,            { jos nr ir bait— kiekis }
      op_liko: longint; { tiek operacij— dar reikia ¨vykdyti }
      ivykdyta: boolean; { ar ¨vykdyta prie˛ tai buvusi opercija }
begin
  { su‘inome atminties kiek¨ ir neatlikt— operacij— skai‡i— }
  N := dydis;
  op_liko := skaicius;
  { inicializuojame atmint¨ }
  bloku_kiekis := 1;
  atm[1].bloko_dydis := N;
  atm[1].rasymo_op_nr := 0;
  ivykdyta := true;
  while ivykdyta and (op_liko > 0) do
    begin
      oper (op, nr, b);  { su‘inoma tolesn‚ operacija }
      if op = 'T'
         then begin { i˛trinami duomenys }
                atm[nr].rasymo_op_nr := 0;
                trinti (nr);
              end
         else irasyti (nr, b, ivykdyta);
      op_liko := op_liko - 1;
    end;
  baigti;
end.