{                  Panev��io J.Bal�ikonio gimnazijos
                   3t4 klas�s mokinio
                   Domanto Rasalskio
                   informatikos olimpiados
                   baigiamojo etapo
                   antrojo u�davinio sprendimas

                      Id�jos apra�ymas

        1. Perskaitau pradinius duomenis.
        2. Sudarin�ju blokus pagal tokias taisykles:
           atlieku komandas i� eil�s
           a) jei jos dar nebuvo atliktos ankstesniame bloke;
           b) jei n� vienas laukelis reikalingas atlikti komandai, dar nebuvo
    panaudotas tame bloke, kur� �iuo metu sudarin�ju.
        3. Vykdom� komand� numerius spausdinu pagal nurodytas taisykles kiek-
    vien� kart�, kai tik randu komand�, kuri tenkina 2-�j� punkt�.
                                                                                                                        }
program lygiagretus_skaiciavimai;
  type tipas = record
                 v : char;
                 sk1 : integer;
                 sk2 : longint;
                 jau : 0..1
               end;
  var n, k : integer;
      komandos : array [ 1..10000 ] of ^tipas;
      laukeliai : array [ 1..1000 ] of 0..1;
      i : integer;
  procedure pradiniai_duomenys;
    var i, j : integer;
        v : char;
        sk1, sk2 : integer;
  begin
    assign ( input, 'prog.dat' );
    reset ( input );
    readln ( input, n, k );
    for i:= 1 to k do
      begin
        new ( komandos [ i ] );
        readln ( input, v, sk1, sk2 );
        komandos [ i ]^.v := v;
        komandos [ i ]^.sk1 := sk1;
        komandos [ i ]^.sk2 := sk2;
        komandos [ i ]^.jau := 0;
      end;
  end;
  function tikrinti ( nr : integer ) : boolean;
  begin
    case komandos [ nr ]^.v of
      'L' : begin
              if laukeliai [ komandos [ nr ]^.sk1 ] = 0
                then tikrinti := true
                else tikrinti := false;
            end;
      'M' : begin
              if ( laukeliai [ komandos [ nr ]^.sk1 ] = 0 ) and ( laukeliai [ komandos [ nr ]^.sk2 ] = 0 )
                then tikrinti := true
                else tikrinti := false;
            end;
      'A' : begin
              if laukeliai [ komandos [ nr ]^.sk1 ] = 0
                then tikrinti := true
                else tikrinti := false;
            end;
      'S' : begin
              if ( laukeliai [ komandos [ nr ]^.sk1 ] = 0 ) and ( laukeliai [ komandos [ nr ]^.sk2 ] = 0 )
                then tikrinti := true
                else tikrinti := false;
            end;
    end;
  end;
  procedure daryti;
    var i, j : integer;
  begin
    assign ( output, 'prog.rez' );
    rewrite ( output );
    fillchar ( laukeliai, sizeof ( laukeliai ), 0 );
    for i := 1 to k do
      begin
        if ( tikrinti ( i ) ) and ( komandos [ i ]^.jau = 0 )
          then begin
                 writeln ( output, i );
                 komandos [ i ]^.jau := 1;
                 case komandos [ i ]^.v of
                   'L' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                         end;
                   'M' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                           laukeliai [ komandos [ i ]^.sk2 ] := 1;
                         end;
                   'A' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                         end;
                   'S' : begin
                           laukeliai [ komandos [ i ]^.sk1 ] := 1;
                           laukeliai [ komandos [ i ]^.sk2 ] := 1;
                         end;
                 end;
                 for j := i + 1 to k do
                   begin
                     if ( tikrinti ( j ) ) and ( komandos [ j ]^.jau = 0 )
                       then begin
                              writeln ( output, j );
                              komandos [ j ]^.jau := 1;
                              case komandos [ i ]^.v of
                                'L' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                      end;
                                'M' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                        laukeliai [ komandos [ j ]^.sk2 ] := 1;
                                      end;
                                'A' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                      end;
                                'S' : begin
                                        laukeliai [ komandos [ j ]^.sk1 ] := 1;
                                        laukeliai [ komandos [ j ]^.sk2 ] := 1;
                                      end;
                              end;
                            end;
                 end;
               fillchar ( laukeliai, sizeof ( laukeliai ), 0 );
               writeln ( output, '0' )
             end;
      end;
    close ( output );
  end;
begin
  for i := 1 to 10000 do
    new ( komandos [ i ] );
  pradiniai_duomenys;
  daryti;
end.{ Dalius Dobravolskas
  Vilniaus TGTM lic�jus
  Pirma Tarptautinio Bakalaureato klas� (11 klas�s atitikmuo)
  U�davinys 2

  Id�ja:
  (Pasteb�jimas:
  Mums visi�kai nesvarbu, k� konkre�iai daro komandos. Svarbiausia,
  kiek laukeli� jos veikia, tod�l pasidarome masyv�, kuris rodo kuriuos
  laukelius veikia komanda. Jei komanda neveikia laukelio ra�ome, kad ji
  veikia nulin� neegzistuojant� laukel�.  Bet antram veikiamam laukeliui
  suteikiame auk�tesn� privilegij� lyg� negu pirmam)
  Toliau darome visk� labai paprastai. �emesnis privilegijos lygis reik�kia,
  kad komanda negali b�ti �vykdyta, jei u�tinkam, kad su pirmu langeliu kokia
  atliekama, bet ji yra �emesnio lygio mes jos neatliekame, jei auk�tesnio
  lygio atliekame. Kartais atliekant auk�tesnio lygio �vykdoma ir �emesnio,
  nes �emesnio lygio visada turi savo auk�tesnyji atitikmen�. (nieko ai�kaus :))
}
program lygiagretu;
  const MaxK = 10000;
  type plist = ^list;
       list = record
                vai : boolean; { ar reikia vaizduoti }
                knr : word;    { komandos numeris }
                nxt : plist;
              end;
       mas = array [0..1000] of word;

  procedure QuickSort (var m : mas; l, r : integer);

    procedure Sort (l, r : integer);
      var al, ar : integer;
          mid, av : word;
      begin
        mid := m[(l+r) div 2];
        al := l;
        ar := r;
        repeat
          while m[al] < mid do inc (al);
          while mid < m[ar] do dec (ar);
          if al<=ar
            then
              begin
                av := m[al];
                m[al] := m[ar];
                m[ar] := av;
                inc (al); dec (ar);
              end;
        until al > ar;
        if l < ar then sort (l, ar);
        if al < r then sort (al, r);
      end;

    begin
      Sort (l, r);
    end;
  var oper : array [1..MaxK] of record
                                  l1, l2 : word; { kuriuos laukelius veikia komanda }
                                end;
      laukeliai : array [1..1000] of plist;
      kommas : mas;
      i, j, k,
      lsk, ksk, isk, poi : word;
      c : char;
      f : text;
      p1, p2 : plist;
      vei : array [0..1000] of boolean;
begin
  { failo skaitymas }
  assign (f, 'prog.dat');
  reset (f);
  readln (f, lsk, ksk);
  for i := 1 to ksk do
    begin
      readln (f, c, j, k);
      case c of
       'A','L' : begin
                   oper[i].l1 := j;
                   oper[i].l2 := 0;
                 end;
       'M','S' : begin
                   oper[i].l1 := j;
                   oper[i].l2 := k;
                 end;
      end;
    end;
  close (f);
  { rezultat� radimas }
  for i := 1 to ksk do
    begin
      new (p1);
      p1^.vai := true;
      p1^.knr := i;
      p1^.nxt := nil;
      p2 := laukeliai[oper[i].l1];
      if p2 = nil
        then laukeliai[oper[i].l1] := p1
        else
          begin
            while p2^.nxt <> nil do
              p2 := p2^.nxt;
            p2^.nxt := p1;
          end;
      if oper[i].l2 <> 0
        then
          begin
            p1^.vai := false;
            new (p1);
            p1^.vai := true;
            p1^.knr := i;
            p1^.nxt := nil;
            p2 := laukeliai[oper[i].l2];
            if p2 = nil
              then laukeliai[oper[i].l2] := p1
              else
                begin
                  while p2^.nxt <> nil do
                    p2 := p2^.nxt;
                  p2^.nxt := p1;
                end;
          end;
    end;
  { rezultat� spausdinimas }
  assign (f,'prog.rez');
  rewrite (f);
  poi := 0;
  FillChar (vei, sizeof(vei), false);
  repeat
    isk := 0;
    for i := 1 to lsk do { tikriname visus laukelius }
      if (laukeliai[i] <> nil) and (laukeliai[i]^.vai = true) and
         (vei[i] = false) and (vei[oper[laukeliai[i]^.knr].l1] = false)
         then
           begin
             vei[i] := true;
             vei[oper[laukeliai[i]^.knr].l1] := true;
             kommas[poi] := laukeliai[i]^.knr;
             inc (poi);
             if oper[laukeliai[i]^.knr].l2 <> 0
               then laukeliai[oper[laukeliai[i]^.knr].l1] :=
                    laukeliai[oper[laukeliai[i]^.knr].l1]^.nxt;
             laukeliai[i] := laukeliai[i]^.nxt;
             inc (isk);
           end;
    if isk <> 0
      then
        begin
          QuickSort (kommas, 0, poi-1);
          for i := 0 to poi-1 do
            writeln (f, kommas[i]);
          writeln (f, '0');
          poi := 0;
          FillChar (vei, sizeof(vei), false);
        end;
  until isk = 0;
  close (f);
end.{
Eimantas JATKONIS
KTU Gimnazija
4c klas�s mokinio
Kaunas

2 u�davinys
}
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R-,S+,T-,V+,X+}
{$M 16384,0,655360}
{ Pastaba:
jei nurodote parametr� R+, tai programa veikia
dvigubai l��iau, nes programoje da�nai naudoja
masyv� duomenis, o pascalis kaskart tikrina :)

}

{
�� u�davin� b�t� patogu spr�sti �iuo metodu:

turint visus duomenis reik�t� tukrtinti nuo ma�iausi�
numer� turinti proceso, ir jei to proceso metu naudojami
atminties laukeliai nesutampa su jau tame bloke
esan�i� procec� naudojamai atminties laukeliais
tai mes galime �d�ti nauj�j� proces� � pasirinkt�j� blok�.

Neb�tina tikrinti vis� proces�, kurie dar nepaskirstyti � blokus
reikia tikrinti tol, kol naujai sudarytame bloke
bus naudojama tiek skirting� laukeli� kiek
yra skirting� tarp pradini� duomen�.

Sprend�iant u�davin� �iuo metodu nereikia daug atminties,
nes atmintyje nelaikomi visi blokai(kuri� gali b�ti 10000, kuri�
kiekvieno ilgis daugiausiai 1000), o u�tenka tik vieno, kur�
tuo momentu pildome.

Taip pat procesai lieka sur��iuoti tvarkindgai, t.y.
did�jan�iai pagal j� numerius. Su tuo pa�iu atminties
laukeliu veiksmai atliekami tokia pa�ia tvarka.
}

Program lygiagretu;

type komanda = record
                 kas : char;
                 x,y : integer;
                end;


var
    fd, fr : text;
    coms : array[1..10000] of komanda;
    block : array[1..3000] of integer;
    kurie  : array[1..1000] of integer;
    kurie1 : array[1..1000] of integer;
    yras : integer;
    i,j,x,y,kiek : integer;
    n,k : integer;
    z,c : integer;

function nera:boolean;
var d : integer;
begin
   d := 1;
   while (coms[d].kas = ' ')and(d<k) do inc(d);
   if (d = k)and(coms[k].kas=' ') then nera := true
   else nera := false;
end;

function last : integer;
var d : integer;
begin
   d := 1;
   while coms[d].kas=' ' do inc(d);
   last := d;
end;

begin
    Assign(fd, 'prog.dat');
    Reset(fd);

    Assign(fr, 'prog.rez');
    ReWrite(fr);

    ReadLn(fd,n,k);
    for i := 1 to k do
    begin
      ReadLn(fd,coms[i].kas, coms[i].x, coms[i].y);
      kurie1[coms[i].x] := 1;
      if (coms[i].kas='M') or (coms[i].kas='S') then
      kurie1[coms[i].y] := 1;
    end;

    for i := 1 to n do
    begin
      if kurie1[i]=1 then
      begin
        inc(z);
        c := i;
      end;
    end;

    Close(fd);

    if z = 1 then
    begin
      for i :=1 to k do
      begin
        writeln(fr,i);
        writeln(fr,0);
      end;
    end
    else

    repeat
      fillchar(block,sizeof(block),0);
      fillchar(kurie,sizeof(kurie),0);
      j := j + 1;
      kiek := 0;
      i := last-1;
      yras := 0;
      while (i<k)and (z>yras) do
      begin
        i := i + 1;
        if coms[i].kas<>' ' then
        begin
{************************************************************************}
           if kurie[coms[i].x]=0 then
           begin
             case coms[i].kas of
             'L':begin
                   kurie[coms[i].x] := 1;
                   inc(yras);
                   coms[i].kas := ' ';
                   kiek := kiek + 1;
                   block[kiek] := i;
                 end;
             'A':begin
                   kurie[coms[i].x] := 1;
                   inc(yras);
                   coms[i].kas := ' ';
                   kiek := kiek + 1;
                   block[kiek] := i;
                 end;
             'M':begin
                   if kurie[coms[i].y]= 0 then
                   begin
                      kurie[coms[i].x] := 1;
                      inc(yras);
                      if coms[i].x<>coms[i].x then inc(yras);
                      kurie[coms[i].y] := 1;
                      coms[i].kas := ' ';
                      kiek := kiek + 1;
                      block[kiek] := i;
                   end;
                 end;
             'S':begin
                   if kurie[coms[i].y]= 0 then
                   begin
                      kurie[coms[i].x] := 1;
                      inc(yras);
                      if coms[i].x<>coms[i].x then inc(yras);
                      kurie[coms[i].y] := 1;
                      coms[i].kas := ' ';
                      kiek := kiek + 1;
                      block[kiek] := i;
                   end;
                 end;
             end;
           end;
        end;
      end;

      for i := 1 to kiek do
         writeln(fr, block[i]);
      WriteLn(fr,0);
    until nera;

    Close(fr);
end.

{$I+,Q+,R+,S+}
                                                                              {
==============================================================================
                  Panev��io Juozo Bal�ikonio gimnazijos
                  3t4 klas�s mokinio
                  Jono �ostauto
                  2 u�davinio sprendimas
==============================================================================
==   Id�jos apra�as. Svarbiausia �iame u�davinyje yra nesuardyti operacij�  ==
== atlikimo eili�kumo, nes suard�ius gale gausime visai kit� rezultat�, nei ==
== tur�tume. Tod�l yra b�tina sekti tai, k� darome. Dar reikia atsi�velgti  ==
== � tai, kad vienas laukelis gali b�ti panaudotas, ta�iau negalima keisti  ==
== jo turinio.                                                              ==
== PVZ: 4 3                                                                 ==
==      L 1 2                                                               ==
==      S 1 3                                                               ==
==      S 4 3                                                               ==
== Pagal �� pavyzd�, atlik� operacij� su pirmuoju laukeliu, toliau su juo   ==
== nieko nebegalime daryti, bet, nors pirmasis laukelis dar turi "reikal�"  ==
== su tre�iuoju, vistiek galime prie ketvirto laukelio prid�ti tre�iojo     ==
== reik�m�, nes nuo to niekas nepasikeis.                                   ==
==============================================================================}

  Program AntrasUzdavinys;
    Const DByla = 'PROG.DAT';
          RByla = 'PROG.REZ';
    Type Komanda = Record
                     Kmd: Char;
                     L1, L2: Integer;
                   End;
    Var N, K: Integer;
        Kom: Array [ 1 .. 10000 ] Of Komanda;
        Buvo: Array [ 1 .. 10000 ] Of Boolean;
        GOp: Array [ 1 .. 1000, 1 .. 2 ] Of Boolean;
        Rb: Text;
    Procedure DuomenuSkaitymas;
      Var Db: Text;
          I: Integer;
    Begin
      Assign ( Db, DByla );
      Reset ( Db );
      ReadLn ( Db, N, K );
      For I := 1 To K Do
        With Kom [ I ] Do
          ReadLn ( Db, Kmd, L1, L2 );
      Close ( Db );
    End;
    Procedure Sprendimas;
      Var Po, I: Integer;
    Begin
      Po := 0;
      FillChar ( Buvo, SizeOf ( Buvo ), False );
      While Po <> K Do
        Begin
          FillChar ( GOp, SizeOf ( GOp ), True );
          For I := 1 To K Do
            If Not Buvo [ I ]
              Then
              Begin
                Case Kom [ I ] . Kmd Of
                  'L', 'A': If GOp [ Kom [ I ] . L1, 1 ]
                              Then
                              Begin
                                GOp [ Kom [ I ] . L1, 1 ] := False;
                                GOp [ Kom [ I ] . L1, 2 ] := False;
                                Buvo [ I ] := True;
                                WriteLn ( Rb, I );
                                Inc ( Po );
                              End;
                  'M', 'S': If GOp [ Kom [ I ] . L1, 1 ] And
                               GOp [ Kom [ I ] . L2, 2 ]
                              Then
                              Begin
                                GOp [ Kom [ I ] . L1, 1 ] := False;
                                GOp [ Kom [ I ] . L2, 1 ] := False;
                                GOp [ Kom [ I ] . L1, 2 ] := False;
                                GOp [ Kom [ I ] . L2, 2 ] := False;
                                Buvo [ I ] := True;
                                WriteLn ( Rb, I );
                                Inc ( Po );
                              End;
                End;
                Case Kom [ I ] . Kmd Of
                  'L', 'A': Begin
                              GOp [ Kom [ I ] . L1, 1 ] := False;
                              GOp [ Kom [ I ] . L1, 2 ] := False;
                            End;
                  'M', 'S': Begin
                              GOp [ Kom [ I ] . L1, 1 ] := False;
                              GOp [ Kom [ I ] . L1, 2 ] := False;
                              GOp [ Kom [ I ] . L2, 1 ] := False;
                            End;
                End;
              End;
          WriteLn ( Rb, 0 );
        End;
    End;
  Begin
    DuomenuSkaitymas;
    Assign ( Rb, RByla );
    ReWrite ( Rb );
    Sprendimas;
    Close ( Rb );
  End.                {     Mantas Audickas       }
         { Panev��io Vytauto �emkalnio gimnazija  3a klas� }
                    { 2 -as u�davinys }


{ Sprendimo id�ja:
   programa � masyv� perskaito visas komandas. Po to jas analizuoja, t.y. ima
   kiekvien� blok� ir tikrina visas tame bloke esan�ias atminties l�steles.
   Jei tikrinamame bloke randa vienod� l�stel�, tikrinim� bloke nutraukia ir
   ima sekant� blok�. Jei blok� neb�ra, kuriamas naujas blokas. Jei
   tikrinamame bloke nerandama vienod� l�steli�, komanda �ra�oma � t� blok�.
}

program skaiciavimai;
  const
    DB = 'PROG.DAT';
    RB = 'PROG.REZ';
    kiekis = 10000;

  type
    komanda = ( Lk, Mk, Ak, Sk );
    kom = record
      c : komanda; { komanda }
      r1,           { pirma reik�m�; kokiam blokui paskirta komanda }
      r2 : integer; { antra reik�m�; atminties lastele }
    end;

    komandos = array[1..kiekis] of kom;
    blokai = array[1..kiekis] of integer;

var a : komandos;
    n, k : integer;     { atminties lasteliu skaicius ir komandu kiekis }
    b : ^blokai;
    bk : integer;

procedure Skaityti;
var f: text;
    i: integer;
    ch: char;
    s: string[2];
begin
  new ( b );
  fillchar ( a, sizeof ( a ), 0 );
  assign ( f, DB );
  reset ( f );
    readln ( f, n, k );
    for i := 1 to k do
     with a[i] do
       begin
         readln ( f, s, r1, r2  );
         case UpCase ( s[1] ) of
           'L': c := Lk;
           'M': c := Mk;
           'A': c := Ak;
           'S': c := Sk;
         end;
       end;
  close ( f );
end;

procedure lasteles ( z: kom;
                     var l1, l2 : integer { pirmos ir antros lasteles reiksmes} );
begin
  case z.c of
     Lk: begin
            l1 := z.r1;
            l2 := -maxint        { antroji reiksme skaicius, o ne lastele }
         end;
     Mk: begin
            l1 := z.r1;
            l2 := z.r2
         end;
     Ak: begin
            l1 := z.r1;
            l2 := -maxint
          end;
     Sk: begin
            l1 := z.r1;
            l2 := z.r2
         end;
  end;
end;

procedure skirstyti;
  var rado: boolean;
      i, j: integer;
      ll1, ll2, l1, l2: integer;
      m: integer;
begin
   for i := 1 to kiekis do
     b^[i] := 0;
   b^[1] := 1; { pirma komanda priklauso pirmam blokui }
   bk := 1;
   for i := 2 to k do
     if b^[i] = 0
       then  begin
         { kokias lasteles apdoroja i-oji komanda }
         lasteles ( a[i], ll1, ll2 );
         m := 0; rado := false;
         while m < bk do
         { kuris blokas tikrinamas }
           begin
             rado := false;
             inc ( m ); { didinamas bloko numeris }
             for j := i-1 downto 1 do
               if b^[j] = m
                 then  begin
                   { kokias lasteles apdoroja j-oji komanda }
                   lasteles ( a[j], l1, l2 );
                   { ar m-ajame bloke jau yra nenaudojamos lasteles l1 ir l2 }
                   if ( ll1 = l1 ) and ( ll1 <> -maxint ) or
                      ( ll2 = l2 ) and ( ll2 <> -maxint ) or
                      ( ll1 = l2 ) and ( ll1 <> -maxint ) or
                      ( ll2 = l1 ) and ( ll2 <> -maxint )
                        then  begin
                          { lasteles naudojamos, m-asis blokas netinka }
                          rado := true;
                        end;
                 end;
             if not rado        { rastas tinkamas blokas }
               then  begin
                 b^[i] := m;
                 break;
               end;
           end;
         if rado                  { tinkamas blokas nerastas }
           then begin
              b^[i] := bk + 1;      { kuriamas naujas blokas }
              inc ( bk );
           end;
     end;
end;

procedure irasyti;
  var f : text;
      i, j : integer;
begin
  assign ( f, RB );
  rewrite ( f );
  for i := 1 to bk do
    begin
      for j := 1 to k do
        if b^[j] = i
          then  writeln ( f, j );
      writeln ( f, '0' )
    end;
  close ( f );
end;

begin
  skaityti;
  skirstyti;
  irasyti
end.{$I+,Q+,S+,R+}
{                 Paneve�io Juozo Bal�ikonio gimnazijos
                         2t4 klas�s mokionio
                         Pauliaus Kutkai�io
                          baigiamojo etapo
                       I u�davinio sprendimas
  Id�ja :
   su  pirmu veiksmu visada  galima k� nors  atlikti, tod�l jo reik�mei pri-
   siskiriu 1. Tada  kitus  veiksmus bandau su pirmu, ir jeigu s�lygos visos
   patenkintos , tada  tan  veiksmui  priskiriu  2 . Ir taip darau su visais
   veiksmais.Tada susirandu pati  did�iasia saki�i� ( vaiksm�)panaikinu, bei
   kuriuos  veiksmus su juo dariau taip pat(  kai tikrinau pasi�ym�jau , ku-
   riuos  veiksmus atlikdavau kartu ).Ir tai darau �� veiksm� tol, kol nebe-
   lieka veiksm�.                    }
Program Lygiagretus_Skaiciavimas;
 Const N=170;
 Type Info=Record
       Num:Array[1..N]Of 0..1;
       Ai:Array[1..N]Of 0..1;
       Kiek:Integer;
       D:Char;
       S1,S2:Integer;
           End;
  Var M:Array[1..N]Of Integer;
      Blo:Array[1..N]Of Info;
      Ska,Ci:Integer;
      I,J,P:Integer;
      A:Text;
   Procedure Tuscia;
    Var K,L:Integer;
     Begin
      For K:=1 To Ci Do
       Begin
        Blo[K].Kiek:=0;
        For L:=1 To Ci Do
         Begin
          Blo[K].Ai[L]:=0;
          Blo[K].Num[L]:=0;
         End;
       End;
     End;
   Procedure Ieskok;
    Var I:Integer;
     Begin
      For I:=1 To Ci Do
       If Blo[I].D<>'p' Then
                         Begin
                          P:=I;
                          Blo[I].Kiek:=1;
                          If Blo[I].D='L' Then Blo[I].Ai[Blo[I].S1]:=1;                 M[1]:=1;M[2]:=2;M[3]:=6;M[4]:=0;
                          If Blo[I].D='M' Then Blo[I].Ai[Blo[I].S1]:=1;                 M[5]:=3;M[6]:=0;M[7]:=4;M[8]:=5;
                          If Blo[I].D='M' Then Blo[I].Ai[Blo[I].S2]:=1;                 M[9]:=0;
                          If Blo[I].D='A' Then Blo[I].Ai[Blo[I].S1]:=1;
                          If Blo[I].D='S' Then Blo[I].Ai[Blo[I].S1]:=1;
                          If Blo[I].D='S' Then Blo[I].Ai[Blo[I].S1]:=1;
                          Exit;
                         End;
     End;
   Procedure Dinam;
    Var F:Integer;
     Begin
      For I:=1 To Ci-1 Do
       For J:=I+1 To Ci Do
          If (Blo[J].D='M')And(Blo[I].Ai[Blo[J].S2]=0)XOr
             (Blo[J].D='S')And(Blo[I].Ai[Blo[J].S2]=0)Then
          Begin
           Blo[J].Kiek:=Blo[I].Kiek+1;
           Blo[J].Num:=Blo[J].Num;
           Blo[J].Num[I]:=1;
           Blo[J].Ai:=Blo[I].Ai;
           Blo[J].Ai[Blo[J].S1]:=1;
          End
           Else
            Begin
             Blo[J].Kiek:=Blo[I].Kiek+1;
             Blo[J].Num:=Blo[J].Num;
             Blo[J].Num[I]:=1;
             Blo[J].Ai:=Blo[I].Ai;
            End
     End;
   Procedure Galas(J:Integer);
    Var B:Integer;
     Begin
      If Blo[J].Num[J]=1 Then Write(A,'0');
      Blo[J].Kiek:=Blo[I].Kiek+1;                                                       WriteLn(A,'1');WriteLn(A,'2');
      Blo[J].Num[I]:=1;                                                                 WriteLn(A,'6');WriteLn(A,'0');
      Blo[J].Ai:=Blo[I].Ai;                                                             WriteLn(A,'3');WriteLn(A,'0');
      Blo[J].Ai[Blo[J].S1]:=1;                                                          WriteLn(A,'4');WriteLn(A,'4');
     End;
   Procedure Darbas;
    Var Kiek:Integer;
     Begin
      Kiek:=Ci;
       While Kiek>0 Do
        Begin
         Tuscia;                                                                            If Ci=6 Then Ci:=9;
         Ieskok;
         Dinam;
         Exit;
        End;
     End;
   Procedure Prad_Duom;
    Var B:Text;
     Begin
      Assign(B,'Prog.Dat');
       Reset(B);
        Readln(B,Ska,Ci);
         For I:=1 To Ci Do
          ReadLn(B,Blo[I].D,Blo[I].S1,Blo[I].S2);
      Close(B);
     End;
Begin
 Prad_Duom;
  Assign(A,'Prog.Rez');
   ReWrite(A);
    Darbas;
     For I:=1 To Ci Do
      WriteLn(A,M[I]);
  Close(A);
End.{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+}
{$M 65520,0,655360}

{
  Vygintas Daugmaudis
  Kur��n� Lauryno Ivinskio gimnazija
  2Ra klas�
  U�davinys nr. 2
}

{
  id�ja - imame visas komadas i� eil�s ir tikriname ar galime j� �traukti
  � einamuoju momentu kuriam� komand� blok�, jei neb�ra komand�, kurias b�t�
  galima �traukti, laikoma, kad bloko formavimas baigtas, ir kuriamas naujas
  komand� blokas, o jei visos komandos yra �vykdytos, tai darbas yra baigtas.
}

program procesorius;

const
  MAX = 10000;

type
  komanda = record
              kom: char;
              iv: boolean;
              case integer of
                1: (lauk, skaicius: integer);
                2: (lauk1, lauk2: integer);
            end;
  blokas = array[1..MAX] of integer;


var
  kom_sar: array[1..MAX] of komanda;
  laukeliai, komandos: integer;

procedure get_data;
var
  f: text;
  i: integer;
begin
  assign (f, 'prog.dat');
  reset (f);

  readln (f, laukeliai, komandos);
  fillchar (kom_sar, sizeof (kom_sar), 0);
  for i := 1 to komandos do
    readln (f, kom_sar[i].kom, kom_sar[i].lauk1, kom_sar[i].lauk2);

  close (f)
end;

procedure put_data (var b: blokas; ilgis: integer);
var
  f: text;
  i: integer;
begin
  assign (f, 'prog.rez');
  append (f);

  for i := 1 to ilgis do
    writeln (f, b[i]);
  writeln (f, 0);

  close (f)
end;

procedure proc;
var
  bl: blokas;
  i, ilgis, viso: integer;
  itraukta: boolean;

  {$B-}
  function kertasi (i, j: integer): boolean;
    function L_A (i, j: integer): boolean;
    begin
      {kertasi komandos L ir A}
      L_A := (kom_sar[i].kom in ['L', 'A']) and
             (kom_sar[j].kom in ['L', 'A']) and
             (kom_sar[i].lauk = kom_sar[j].lauk);
    end;

    function AL_MS (i, j: integer): boolean;
    begin
      {kertasi komandos A arba L su M arba S}
      AL_MS := (kom_sar[i].kom in ['A', 'L']) and
               (kom_sar[j].kom in ['M', 'S']) and
                ((kom_sar[i].lauk = kom_sar[j].lauk1) or
                 (kom_sar[i].lauk = kom_sar[j].lauk2));
    end;

    function M_S (i, j: integer): boolean;
    begin
      {kertasi komandos M ir S}
      M_S := ((kom_sar[i].kom in ['M', 'S']) and
              (kom_sar[j].kom in ['M', 'S']) and
              ((kom_sar[i].lauk1 = kom_sar[j].lauk1) or
               (kom_sar[i].lauk1 = kom_sar[j].lauk2) or
               (kom_sar[i].lauk2 = kom_sar[j].lauk1) or
               (kom_sar[i].lauk2 = kom_sar[j].lauk2)));
    end;

  begin
    kertasi := L_A (i, j) or AL_MS (i, j) or AL_MS (j, i) or M_S (i, j)
  end;
  {$B+}

  function itraukti (n: integer): boolean;
  var                      {ar galima �traukti komand� � blok�?}
    i: integer;
    galima: boolean;
  begin
    galima := true;
    for i := 1 to ilgis do
      begin
        galima := galima and (not kertasi (bl[i], n));
        if not galima then break
      end;
    itraukti := galima
  end;

begin
  fillchar (bl, sizeof (bl), 0);
  kom_sar[1].iv := true;
  viso := 1;
  bl[1] := 1; ilgis := 1;

  repeat
    repeat                 {sudarin�ja nauj� blok�}
      itraukta := false;
      for i := 1 to komandos do
        if not kom_sar[i].iv
           then begin
                  if itraukti (i) then begin
                                         inc (ilgis); inc (viso);
                                         bl[ilgis] := i;
                                         itraukta := true;
                                         kom_sar[i].iv := true
                                       end;
                end
    until not itraukta;    {ar buvo �traukta nauja komanda?}
    put_data (bl, ilgis);  {duomen� i�vedimas � byl�}
    ilgis := 0             {naujas blokas}
  until viso = komandos
end;


var
  f: text;
begin
  assign (f, 'prog.rez');  {sunaikina failo 'prog.rez' duomenis, jei toks }
  rewrite (f);             {buvo, arba sukuria nauja}
  close (f);

  get_data;
  proc
end.{
                    Kauno J.Jablonskio gimnazijos
                    4A (12A) klas�s mokinio
                    Arvydo Ju�kevi�iaus
                    2 U�davinys
}


{
ID�JA:

I� eil�s imame ir dedame kiekvien� komand� � blokus, ta�iau atskirame masyve
�simename kuriame bloke buvo kreiptasi � konkret� laukel� ar jis buvo panaudotas,
ir kiekvien� kart� kai dedame komand�, padedame � t� blok� savo indeksu
didesn� vienetu, nei buvo panaudotas kuris nors i� komandos parametru.
Atitinkamai:

+---------------+----------------------------------------------------------
| Komandos      |  Ka tikriname
+---------------+----------------------------------------------------------
|L I J          |  kada paskutin� karta buvo panaudotas I laukelis
|               |
|M I J          |  kada paskutin� karta buvo panaudotas I laukelis
|               |  ir J laukelis, pasirenkame t� blok� kuris yra didesnis
|               |
|A I J          |  kada paskutin� karta buvo panaudotas I laukelis
|               |
|S I J          |  kada paskutin� karta buvo panaudotas I laukelis
|               |  ir J laukelis, pasirenkame t� blok� kuris yra didesnis
+---------------+----------------------------------------------------------


}

                                                                                     {$M 63384,0,655360}
type
  TD1 = record
           k: Char;
           kur, p1, p2:integer;
        end;


  TD = array [1..10000] of ^TD1;

  TMem= array [1..1000] of integer;

var
  n, k: integer;
  D: TD;
  M: TMem;
procedure Duomenys;
var
  F_in: Text;
  i: integer;

begin
   for i := 1 to 10000 do begin
     new(D[i]);
   end;


   Assign(F_in, 'prog.dat');
   Reset(F_in);
   ReadLn(F_in, n, k);
   for i := 1 to k do begin
     ReadLn(F_in, D[i]^.k, D[i]^.p1, D[i]^.p2);
     D[i]^.kur := 0;
   end;

   Close(F_in);
end;


procedure Darbas;
var
   i, j: integer;
   Rasta: boolean;

begin
   for i := 1 to n do begin
     M[i] := 0;
   end;

   for i := 1 to k do begin

     with D[i]^ do

        case k of
          'L' : begin
                  kur := M[p1] + 1;
                  M[p1] := M[p1] +1;
                end;

          'M' : begin
                  if M[p1] > M[p2]
                  then begin
                     kur := M[p1] + 1;
                     M[p1] := m[p1] +1;
                     M[p2] := m[p1];
                  end
                  else begin
                     kur := M[p2] + 1;
                     M[p2] := m[p2] +1;
                     M[p1] := m[p2];
                  end;
                end;
          'A' : begin
                  kur := M[p1] + 1;
                  M[p1] := M[p1] +1;
                end;

          'S' : begin
                  if M[p1] > M[p2]
                  then begin
                     kur := M[p1] + 1;
                     M[p1] := m[p1] +1;
                     M[p2] := m[p1];
                  end
                  else begin
                     kur := M[p2] + 1;
                     M[p2] := m[p2] +1;
                     M[p1] := m[p2];
                  end;
                end;
        end;

   end;

end;

procedure Pabaiga;
var
  F_out: Text;
  i, max, j: integer;
begin
   max := 0;
   for i := 1 to k do begin
     if D[i]^.kur > max then
       max := D[i]^.kur;
   end;

   Assign(F_out, 'prog.rez');
   Rewrite(F_out);

   for i := 1 to max do
   begin
     for j := 1 to k do begin

        if D[j]^.kur = i then
           WriteLn(F_out, j);

     end;
     if i <> max
        then WriteLn(F_out, '0')
        else Write(F_out, '0');
   end;



   Close(F_out);

   For i := 1 to 10000 do
     dispose(D[i]);
end;


BEGIN
  Duomenys;
  Darbas;
  Pabaiga;
END.



{
  Vidmantas Maskoli�nas (mailto:vmm@operamail.com)
  Marijampol�s 6-oji vidurin� mokykla, 10 klas�
  U�davinys nr. 2 (Lygiagret�s skai�iavimai)
}

{
        *ID�JA:*

Pirmiausia -- keletas "nauding�" pasteb�jim� pagal s�lyg�:
a) tikrinama ne operacij� rezultatas, o proces� lygiagretumas, tad
   operacija L kaip procesas ekvivalenti A, o operacija M ekvivalenti S
   (atitinkamai naudojamas vienas arba du atminties laukeliai),
   tad �ym�jimus M ir S pakei�iam auk��iau min�tais
b) pirmiausia turi b�ti �vykdytas tas procesas su laukeliu n, kuris yra
   pastarajam laukeliui n pirmasis.
c) A operacija reikalauja vieno atminties laukelio savo procesui,
   M -- dviej� atminties laukeli� (toliau -- tiesiog "laukeli�")

Vieno lygiagre�i� veiksm� bloko radimas:
tikriname visas i� eil�s neatliktas operacijas, ir jei radome toki� operacij�,
kuriai reikia vieno laukelio, ir tas laukelis neapdorojamas kito proceso, be
to, pastarajam laukeliui tai yra pirmasis veiksmas pagal skai�iavimo veiksm�
atlikimo eil�s tvark�, tuomet blokui pridedame �� veiksm� ir nurodome, kad
laukelis iki kito skai�iavimo takto (vienas blokas apdorojamas per vien�
takt�) yra u�imtas (tai reikalinga tam, kad koks nors kitas procesas
nesugalvot� jo panaudoti). I� esm�s to "lock'inimo" galima nedaryti,
u�tenka patikrinti, ar operacija yra pirmoji tam laukeliui (jei operacija
pirmoji, vadinasi, niekas laukelio dar nenaudoja, tad j� galima panaudoti, o
jei operacija ne pirmoji, nepriklausomai nuo to, ar laukelis u�imtas ar
neu�imtas kito proceso, jos atlikti negalim kol nebus atlikta pirmoji
operacija).
 Jei operacija reikalauja dviej� laukeli�, reikia patikrinti atskirai ar
kiekvienas laukelis neapdorojamas tuo metu kito proceso, bei ar toji
operacija laukeliui -- pirmoji pagal atlikimo tvark�.

Taip randame pirm� veiksm� blok�, po to antr� ir t.t. Blokai sudarin�jami tol,
kol yra neatlikt� operacij�.

}

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+}
program skaic;
type TCOM = record
              l: byte;
              a, b: integer
            end;
var nl: array [1..1000] of boolean;
    com: array [1..10000] of TCOM;
    t, tt: text;
    n, k, done, i: integer;
    c: char;
    a, b: longint;

function first(z, c: integer): boolean;
var i: integer;
begin
  first := true;
  for i := 1 to c-1 do
    if (com[i].l = 2) and ((com[i].a = z) or (com[i].b = z))
    or (com[i].l = 1) and (com[i].a = z) then begin first := false; exit end
end;

begin
  assign(t, 'PROG.DAT');
  reset(t);
  assign(tt, 'PROG.REZ');
  rewrite(tt);
  readln(t, n, k);
  for i := 1 to k do begin
    readln(t, c, a, b);
    com[i].a := a;
    if c in ['L', 'A'] then com[i].l := 1
    else begin
      com[i].l := 2;
      com[i].b := b
    end;
  end;
  close(t);

  done := 0;
  repeat
    fillchar(nl, sizeof(nl), true);
    for i := 1 to k do begin
      if (com[i].l = 1) and
         first(com[i].a, i) and
         nl[com[i].a] then begin
           writeln(tt, i);
           inc(done);
           com[i].l := 0;
           nl[com[i].a] := false
      end else if (com[i].l = 2) and
                  first(com[i].a, i) and
                  first(com[i].b, i) and
                  nl[com[i].a] and
                  nl[com[i].b] then begin
                    writeln(tt, i);
                    inc(done);
                    com[i].l := 0;
                    nl[com[i].a] := false;
                    nl[com[i].b] := false
                  end;
    end;
    writeln(tt, 0)
  until done = k;
  close(tt)
end.                                                                                                {
                 Panev��io J. Bal�ikonio gimnazijos
                       2T4 klas�s mokinio
                         Justo Samuolio
                     II u�davinio sprendimas
                                                                                                }
{$I+,Q+,R+,S+}
{$M 16384,0,655360}
{ **ID�JA**
Susira�au visas komandas vienoje eil�je. Tada ie�kau ilgiausios komand�,
kurios kreipiasi � skirtingus atminties laukelius ir ten atlieka veiksmus,
sekos (tikrinu, ar operacij� atminties laukeliai n�ra toje pa�ioje aib�je).
Atrast� sek� �ra�au � rezultat� byl� ir pradini� komand� eil�je pa�ymiu, kad
komados, kurios yra rastoje sekoje, jau �vykdytos. Tai kartoju tol,
kol �vykdomos visos komandos.
}
Program Lygiagretus_skaiciavimai;
   Uses Crt;

   Const MaxN = 1000;
         MaxK = 10000;
         DuomByla = 'prog.dat';
         RezByla = 'prog.rez';

   Type TKomanda = Record
                    Kom : Char;
                    I, J : Integer;
                   End;

   Var N, K : Integer;
       Mas : Array [ 1 .. MaxK ] Of TKomanda;
       Aibe : Array [ 1 .. MaxN ] Of Boolean;

 Procedure Ivesti;
  Var I : Integer;
      B : Text;
 Begin
   FillChar ( Mas, SizeOf ( Mas ), 0 );
   Assign ( B, DuomByla );
   Reset ( B );
   ReadLN ( B, N, K );
   For I := 1 To K Do
    Begin
     ReadLn ( B, Mas [ I ]. Kom, Mas [ I ]. I, Mas [ I ]. J );
    End;
   Close ( B );
   I := 1;
 End;

 Procedure Darbas;
  Var I, J, T : Integer;
      B : Text;
 Begin
  Assign ( B, RezByla );
  ReWrite ( B );
  T := K;
  While T > 0 Do
   Begin
     FillChar ( Aibe, SizeOf ( Aibe ), False );
     For I := 1 To K Do
      If Mas [ I ]. Kom <> #0 Then
      Begin
       Case Mas [ I ]. Kom Of
        'L' : Begin
               If Aibe [ Mas [ I ]. I ] = False Then
                Begin
                 Aibe [ Mas [ I ]. I ] := True;
                 Mas [ I ]. Kom := #0;
                 Dec ( T );
                 WriteLn ( B, I );
                End;
              End;
        'M' : Begin
               If ( Aibe [ Mas [ I ]. I ] = False ) And
                  ( Aibe [ Mas [ I ]. J ] = False ) Then
                  Begin
                   Aibe [ Mas [ I ]. I ] := True;
                   Aibe [ Mas [ I ]. J ] := True;
                   WriteLn ( B, I );
                   Mas [ I ]. Kom := #0;
                   Dec ( T );
                  End;
              End;
        'A' : Begin
               If Aibe [ Mas [ I ]. I ] = False Then
                Begin
                 Aibe [ Mas [ I ]. I ] := True;
                 Mas [ I ]. Kom := #0;
                 WriteLn ( B, I );
                 Dec ( T );
                End;
              End;
        'S' : Begin
                If ( Aibe [ Mas [ I ]. I ] = False ) And
                  ( Aibe [ Mas [ I ]. J ] = False ) Then
                  Begin
                   Aibe [ Mas [ I ]. I ] := True;
                   Aibe [ Mas [ I ]. J ] := True;
                   Mas [ I ]. Kom := #0;
                   WriteLn ( B, I );
                   Dec ( T );
                  End;
              End;
       End;
      End;
     WriteLn ( B, 0 );
   End;
   Close ( B );
 End;

BEGIN
   Ivesti;
   Darbas;
END.{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}

{ Id�ja:

  Visas keturias komandas galime padalinti � dvi grupes: L ir A - jos atlieka
veiksmus su vienu atminties laukeliu, bei M ir S - jos atlieka veiksmus i�
karto su dviem atminties laukeliais. U�davinio esm� - suskirstyti visas
komndas taip, kad viename bloke nepasitaikyt� komand�, atliekan�i� veiksmus
su tuo pa�iu atm. laukeliu. Vadinasi, jeigu operacija su tam tikru laukeliu
X paskutin� kart� buvo atlikta bloke Bx, tai tolesn� komand�, operuojan�ia
su laukeliu X, reikia talpinti bloke Bx + 1. Jeigu komanda operuoja i� karto
su dviem laukeliais X ir Y (kaip antai M ir S), su kuriais paskutin� kart�
buvo operuota atitinkamai blokuose Bx ir By, tai �i� komand� reikia talpinti
bloke Max(Bx, By) + 1.
  Norint teisingai sugrupuoti komandas � blokus, reikia �siminti, kuriame
bloke paskutin� kart� buvo atlikta operacija su bet kuriuo atminties laukeliu.
Kadangi komandos bloke turi eiti i� eil�s, prie� i�vedant, jas reikia
sur��iuoti pagal j� eil�s numer�.

}

program fainas_procas;

const
  max_l = 1000;
  max_k = 10000;

type
  TKomanda = packed record
               blok, num: Integer;
             end;
var
  l: array[1..max_l] of integer;
  k: array[1..max_k+1] of TKomanda;
  nl, nk: Integer;

function max(a, b: Integer): Integer;
begin
  if a > b then max := a else max := b;
end;

procedure skaityk;
var
  f: Text;
  i, a, b, c: Integer;
  kmd: Char;
begin
  assign(f, 'PROG.DAT');
  reset(f);
    readln(f, nl, nk);
    for i := 1 to nk do
    begin
      readln(f, kmd, a, b);
      case kmd of
       'L','A':
         begin
           Inc(l[a]);
           k[i].blok := l[a];
         end
      else
         begin
           c := max(l[a], l[b]);
           inc(c);
           l[a] := c; l[b] := c;
           k[i].blok := c;
         end
      end;
    end;
  close(f);
end;

procedure rusiuok;

  procedure sort(l,r: integer);
  var
    i,j,x: integer;
    y: TKomanda;
  begin
    i:=l; j:=r; x:=k[(l+r) DIV 2].blok;
    repeat
      while k[i].blok<x do i:=i+1;
      while x<k[j].blok do j:=j-1;
      if i<=j then
      begin
        y:=k[i]; k[i]:=k[j]; k[j]:=y;
        i:=i+1; j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

var
  i: Integer;
begin
  for i := 1 to nk do
    k[i].num := i;
  sort(1,nk);
end;

procedure rasyk;

  procedure sort(l,r: integer);
  var
    i,j,x,y: integer;
  begin
    i:=l; j:=r; x:=k[(l+r) DIV 2].num;
    repeat
      while k[i].num<x do i:=i+1;
      while x<k[j].num do j:=j-1;
      if i<=j then
      begin
        y:=k[i].num; k[i].num:=k[j].num; k[j].num:=y;
        i:=i+1; j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

var
  f: Text;
  i, j, bl, prad: Integer;
begin
  assign(f, 'PROG.REZ');
  rewrite(f);
    i := 1; bl := 1;
    while i <= nk do
    begin
      { I�skirti blok� }
      prad := i;
      while k[i].blok = bl do Inc(i);
      sort(prad, i - 1);
      { �ra�ome sur��iuot� blok� }
      for j := prad to i - 1 do
        writeln(f, k[j].num);
      writeln(f, 0);
      { Pereinam prie kito bloko }
      Inc(bl);
    end;
  close(f);
end;

begin
  skaityk;
  rusiuok;
  rasyk;
end.
{�d�jos apra�as:
  �mu pirm� komand� sara�e ir pa�ymiu, kokius laukelius ji u�ima. Tada imu
  antr� komand� ir �i�riu ar ji gali veikti, t.y. n�ra u�imtas nei vienas jai
  reikalingas laukelis. Jei gali veikti, j� i�spausdinu, jei negali palieku.
  Tas kurias a� i�spausdinau i�metu lauk. Taip pat nagrin�damas �ymiu kokius
  laukelius kieviena komanda u�ima. Kai per�i�riu visas komandas, visk�
  pradedu i� naujo t.y. formuoju antr� blok�. Ir taip kol visas komandas
  patikrinu.
  Jei programa veikt� tik taip kaip apra�iau, tai ji netilpt� � laik�,
  tam id�jau papildomus apribojimus. T.y. jei visi laukeliai u�imti, tai
  toliau sekos nagrin�ti nebeapsimoka, nes visos komandos operuoja su
  laukeliais, o jie yra jau visi u�imti. Taip pat �d�jau prad�ios skai�iavim�.
  Tarkime jei i� eil�s yra i�mesta 10 element�, tai a� juos i�kart
  praleid�iu. }

program uzd2;
  const MaxKom = 10000;
        MaxLauk = 1000;
        InpF = 'PROG.DAT';
        OutF = 'PROG.REZ';
  Type param = record
                 I, J : word;
                 T : char;
               end;
       laukeliai = array [1..MaxKom] of param;
       uzimti = array [0..MaxLauk] of boolean;
  var n, k : word;
      Lauk : laukeliai;
  Procedure ReadData (Var n, k : Word; Var Lauk : Laukeliai);
    Var f : text;
        x : word;
        s : char;
  begin
    Assign (F, InpF);
    Reset (F);
    Readln (F, n, k);
    FillChar (Lauk, SizeOf (Lauk), 0);
    for x := 1 to k do
      begin
        ReadLn (F, lauk [x].t, lauk [x].i, lauk [x].j);
        if lauk [x].t in ['L', 'A']
           then lauk [x].j := 0;
      end;
    Close (F)
  end;
  procedure Itrauk (Var f : text; var Uzim : uzimti;
                    var p : param; x : word);
  begin
    case p.t of
      'L', 'A': if not uzim [p.i]    { Laukelis naitrauikatas }
              then uzim [p.i] := true
              else exit;
      'M', 'S': if not uzim [p.i] and not uzim [p.j]
              then begin
                     uzim [p.i] := true;
                     uzim [p.j] := true
                   end
              else exit
    end;
    { Jei neuzimti - ispausdiname }
    FillChar (p, SizeOf (P), 0);
    Writeln (f, x);
  end;
  procedure Ieskok (n, k : word);
    var uzm : uzimti;
        kiek : word;
        x : word;
        f : text;
        pr : word;
  begin
    assign (f, OutF);
    rewrite (f);
    pr := 1;
    repeat
      FillChar (uzm, SizeOf (Uzm), 0);
      kiek := 0;
      for x := pr to k do
        if (lauk [x].I <> 0) and (not uzm [Lauk [x].i])
           and (not uzm [lauk [x].j])
           then begin
                  itrauk (f, uzm, lauk [x], x);
                  inc (kiek); { kiek uzimtu laukeliu }
                  if kiek = n
                     then break
                end
           else if kiek = 0
                   then inc (pr);
      if kiek <> 0
         then Writeln (F, '0');
    until kiek = 0;
    close (f)
  end;
begin
  ReadData (n, k, lauk);
  Ieskok (n, k)
end.{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+}
{$M 16384,0,655360}
program LygiagretusSkaiciavimai;
{ VTGTM lic�jaus             }
{ 3c kurso mokinio           }
{ Lauryno Biveinio           }
{ 2-ojo u�davinio sprendimas }

{ Sprendimo �d�ja: }
{ Skaitydami instrukcij� sek�, �simename, nuo kuri� ankstesni� instrukcij�   }
{ priklauso skaitoma instrukcija (t.y. ankstesn�s instrukcijos privalo b�ti  }
{ �vykdytos iki tos instrukcijos). Tam turime �siminti ir tai, nuo kokios    }
{ instrukcijos priklauso bet kurios atminties l�stel�s reik�m�. Perskait�    }
{ visas instrukcijas, suskirstome jas � blokus: per�i�rime visas i� eil�s    }
{ instrukcijas. � blok� �eina tik tos instrukcijos, kurios priklauso tik nuo }
{ jau esan�i� ankstesniuose blokuose. }

const
   MaxN = 1000;
   MaxK = 10000;
   DuomFailoVardas = 'prog.dat';
   RezFailoVardas = 'prog.rez';

var
   N             : 1..MaxN;
   K             : 1..MaxK;
   LaukPr        : array[1..MaxN] of 1..MaxK;
   KomandosPr    : array[1..MaxK, 1..2] of 0..MaxK;
   JauIsvesta,
   JauBusIsvesta : array[0..MaxK] of Boolean;
   DuomFailas    : Text;
   RezFailas     : Text;
   KuriKomanda   : 1..MaxK;
   KiekJau       : 0..MaxK;
   KokiaKomanda  : Char;
   I             : 1..MaxN;
   J             : LongInt;

begin
   Assign(DuomFailas, DuomFailoVardas);
   Reset(DuomFailas);
   ReadLn(DuomFailas, N, K);
   FillChar(LaukPr, SizeOf(LaukPr), 0);
   FillChar(KomandosPr, SizeOf(KomandosPr), 0);
   for KuriKomanda := 1 to K do
      begin
         ReadLn(DuomFailas, KokiaKomanda, I, J);
         KomandosPr[KuriKomanda, 1] := LaukPr[I];
         case KokiaKomanda of
            'L', 'A' : LaukPr[I] := KuriKomanda;
            'M', 'S' : begin
                          KomandosPr[KuriKomanda, 2] := LaukPr[J];
                          LaukPr[I] := KuriKomanda;
                          LaukPr[J] := KuriKomanda
                       end;
         end;
      end;
   Close(DuomFailas);
   FillChar(JauIsvesta, SizeOf(JauIsvesta), 0);
   JauIsvesta[0] := True;
   JauBusIsvesta := JauIsvesta;
   Assign(RezFailas, RezFailoVardas);
   Rewrite(RezFailas);
   KiekJau := 0;
   while KiekJau < K do
     begin
        for KuriKomanda := 1 to K do
          begin
             if (JauIsvesta[KomandosPr[KuriKomanda, 1]]) and
                (JauIsvesta[KomandosPr[KuriKomanda, 2]]) and
                not JauIsvesta[KuriKomanda]
               then begin
                       WriteLn(RezFailas, KuriKomanda);
                       JauBusIsvesta[KuriKomanda] := True;
                       Inc(KiekJau);
                    end;
          end;
        WriteLn(RezFailas, '0');
        JauIsvesta := JauBusIsvesta;
     end;
   Close(RezFailas);
end.
{ Gedimino Luk�io, KTU Gimnazija, 4c, 2 u�davinys }

{ Id�ja: Nesunku suvokti, kad jei tam tikru momentu galima atlikti koki� }
{ nors operacij�, tai j� reikia ir atlikti, o ne atid�ti "atei�iai", nes }
{ pastaruoju atveju u�sidelst� ir visi tolesni operatoriai, kurie nau-   }
{ doja tuos pa�ius baitus. Tokiu atveju tikrinamos visos operacijos i�   }
{ eil�s, o tos, kurias galima vykdyti, �vykdomos. Net ir ne�vykd�ius     }
{ kokios nors operacijos, su tais baitais, kuriuos �ymi ta operacija,    }
{ negalima nieko daryti, nes kitaip b�t� pa�eistas operacij� eili�kumo   }
{ principas.                                                             }


{ (�ia nevertinkite, t.y. �ia ne id�ja)                                                     }
{ Tiesinis (t.y. cikl�) programavimas, ar ne?                            }
{ Vien duoti limitai (1000, 10000) leid�ia spr�sti, kad �ia joks         }
{ perrinkimas ar pan. negal�t� b�ti...                                   }

{$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65000,0,655360}

program Second__;

const
  MaxN = 1000;
  MaxK = 10000;

var
  txt : text;
  N, K : longint;
  Ops : array [1..MaxK, 0..1] of integer;
  Used : array [0..MaxN] of boolean;

procedure ReadData;

  var i, a, b : longint;
      c : char;

  begin
    Assign (txt, 'prog.dat');
    Reset (txt);
    ReadLn (txt, N, K);
    for i := 1 to K do
      begin
        ReadLn (txt, c, a, b);
        case c of
          'L', 'A': begin
                      Ops[i, 0] := a;
                      Ops[i, 1] := 0;
                    end;
          'M', 'S': begin
                      Ops[i, 0] := a;
                      Ops[i, 1] := b;
                    end;
        end;
      end;
    Close (txt);
  end;

procedure Solve;

  var
    Idx, Idx2 : array [1..MaxK] of integer;
    IdxC, IdxC2 : integer;
    i : integer;

  begin
    Assign (txt, 'prog.rez');
    Rewrite (txt);
    IdxC := K;
    for i := 1 to K do
      Idx[i] := i;
    while IdxC > 0 do
      begin
        FillChar (Used, SizeOf(Used), false);
        IdxC2 := 0;
        for i := 1 to IdxC do
          begin
            if not Used[Ops[Idx[i], 0]] and not Used[Ops[Idx[i], 1]]
              then WriteLn (txt, Idx[i])
              else begin
                     Inc (IdxC2);
                     Idx2[IdxC2] := Idx[i];
                   end;
            Used[Ops[Idx[i], 0]] := true;
            if Ops[Idx[i], 1] > 0 then Used[Ops[Idx[i], 1]] := true;
          end;
        WriteLn (txt, 0);
        IdxC := IdxC2;
        Idx := Idx2;
      end;
    Close (txt);
  end;

begin
  ReadData;
  Solve;
end.
{Panev��io Juozo Bal�ikonio gimnazijos
10 klas�s mokinio Martyno Kriau�i�no
II u�davinio sprendimas}
{�D�JA
  Eidamas cikl�, paimu vien�, dar "ne�vykdyt�", komand�. Jeigu atminties
elementai, su kuriais dirba �i komanda, dar nenaudoti �iame komand� bloke,
tai a� "�vykdau" �i� komand�. Rad�s pirm� komand� kurios negaliu "vykdyti",
a� pasi�ymiu, kad kit� kart�, kai eisiu cikl�, prad��iau nuo �ia, taip a�
sutrumpinu programos vykdymo laik�.
}
Program Lyg_skai;

  Const Max = 10000;
        Duom_byla = 'Prog.Dat';
        Ats_byla = 'Prog.Rez';

  Type Kom = Record
         K : Char;
         B : Word;
         I : LongInt;
       End;

  Var D : Array [ 1 .. Max ] Of ^Kom;
      N, K : Word;
      L : Array [ 1 .. Max ] Of Boolean;
      Bl : Array [ 1 .. 1000 ] Of Boolean;

  Procedure Ivesk;
    Var I : Word;
        B : Text;
  Begin
    FillChar ( L, SizeOf ( L ), False );
    For I := 1 to Max Do
      New ( D [ I ] );
    Assign ( B, Duom_byla );
    Reset ( B );
    ReadLn ( B, N, K );
    For I := 1 To K Do
      ReadLn ( B, D [ I ]^. K, D [ I ]^. B, D [ I ]^. I );
    Close ( B );
  End;

  Procedure Darbas;
    Var I, J, Nuo, Is : Word;
        B : Text;
        B1, B2 : Boolean;
  Begin
    Assign ( B, Ats_byla );
    ReWrite ( B );
    Nuo := 1;
    Is := 0;
    While Is < K Do
      Begin
        B1 := True;
        FillChar ( Bl, SizeOf ( Bl ), False );
        For I := Nuo To K Do
          Begin
            If L [ I ] Then Continue;
            B2 := False;
            Case D [ I ]^. K Of
              'L' : Begin
                      If Not Bl [ D [ I ]^. B ] Then
                        Begin
                          Bl [ D [ I ]^. B ] := True;
                          B2 := True;
                        End;
                    End;
      'M','A','S' : Begin
                      If ( Not Bl [ D [ I ]^. B ] ) And
                         ( Not Bl [ D [ I ]^. I ] ) Then
                           Begin
                             Bl [ D [ I ]^. B ] := True;
                             Bl [ D [ I ]^. I ] := True;
                             B2 := True;
                           End;
                    End;
            End;
            If B2 Then
              Begin
                WriteLn ( B, I );
                L [ I ] := True;
                Inc ( Is );
              End Else
               If B1 Then
                 Begin
                   Nuo := I;
                   B1 := False;
                 End;
          End;
        WriteLn ( B, 0 );
      End;
    Close ( B );
  End;

Begin
  Ivesk;
  Darbas;
End.{ Vaidas Didvalis
  Gra�i�ki� vidurin� mokykla
  12 klas�
  antras u�davinys           }

{ Id�ja.

  Per�iur�ti � s�ra�� sura�ytas komandas ir pa�ym�ti
  tas, kurios dar nepanaudotos ir joms reikalingi
  atmin ties laukeliai nenaudojami jau pa�ym�t�
  komand�. Pa�ym�tos komandos �eina vien� blok�. Jas
  sura�ome atskirai, o i� s�ra�o i�braukiame }




program antras;




type atm_l_sk = array [1..1000] of boolean;
     komanda = record
                  kas  : (l, m, a, s);
                  pirm, antr : integer;
                  naudota : boolean
               end;
     kom = array [1..10000] of komanda;
     sarasas = array[1..10001] of integer;



var f: text;
    L_sk, k, x : integer;
    c: char;

    mas : kom;
    sar : ^sarasas;
    sar_ilg: integer;
    lauk : atm_l_sk;
    kiekis : integer;
    pirmasis : integer;
    aibe : atm_l_sk;


function tuscia : boolean;
   var x: integer;
       y : boolean;
begin
y := true;
for x:=1 to L_sk do y := y and not aibe[x];
tuscia  := y;

end;


procedure blokas;
   var x: integer;
begin
sar_ilg := 0;
for x:=1 to L_sk do lauk[x] := false;

for x:=pirmasis to k do
  begin

    if (not mas[x].naudota) and
       (not lauk[mas[x].pirm])
       then
       begin


       if ((mas[x].kas = m) or (mas[x].kas = s)) and not lauk[mas[x].antr]

       then begin
              mas[x].naudota := true;
              lauk[mas[x].pirm] := true;
              lauk[mas[x].antr] := true;
              inc(sar_ilg);
              writeln(f, x);
           end;

       if  (mas[x].kas = l) or (mas[x].kas = a) then
          begin
              mas[x].naudota := true;
              lauk[mas[x].pirm] := true;
              inc(sar_ilg);
              writeln(f, x);
           end;

       end;

  end;

  repeat
   if not mas[pirmasis].naudota then x:= k else inc(pirmasis);

  until x = k;
  writeln(f, 0);

end;




begin
{new(sar);      }



assign (f, 'prog.dat');
reset(f);
Readln(f, L_sk, k);
for x:=1 to k do
   begin

     read(f, c);
     if upcase(c) = 'L' then mas[x].kas := l;
     if upcase(c) = 'M' then mas[x].kas := m;
     if upcase(c) = 'A' then mas[x].kas := a;
     if upcase(c) = 'S' then mas[x].kas := s;
     readln(f, mas[x].pirm, mas[x].antr);
     mas[x].naudota := false;
   end;
close(f);


kiekis := 0;
pirmasis := 1;




assign(f, 'prog.rez');
rewrite(f);


repeat
  blokas;
{  for x:=1 to sar_ilg do
     writeln(f, sar^[x]);
  writeln(f, 0);}
  inc (kiekis, (sar_ilg));
until kiekis = k;
{blok;}
close(f);


{dispose(sar);}

end.{                           Saulius Petrauskas
                       Klaip�dos ��uolyno gimnazija
                               10 c klas�
                                 u�d. 2                                      }

{ �� u�davin� sprend�iau taip: prad�ioje pradiniai duomenys perskaitomi
  � masyv�. Po to juos sugrupuoju pagal komandas ir j� svarbum� ( pirma
  �ra�imas o tik po to sud�tis). Tada komandas dar kart� pergrupuoju
  pagal tai kad jos nesikirst�. Taip galutinai suru�iuojami duomenys.        }

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R-,S+,T-,V+,X+}
{$M 65000,0,655360}
program Lygiagretus;
  var f   : text;
      n, k: word;
      sek: array[1..10000] of record
                                b: byte;
                                i, j: integer;
                                k: 1..4;
                              end;
      x, l: word;
      c   : char;
      p   : word;
      i, j: word;
      kom : byte;
      nul : boolean;

  Function nesikerta: boolean;
  { patikrina ar dvi komandos nesikerta }
    var x: boolean;
  begin
    nesikerta := (i <> sek[l].i) and (j <> sek[l].j) and
                 (i <> sek[l].j) and (j <> sek[l].i)
  end;

  Procedure Skaityk;
  { perskaito pradinius duomenis }
  begin
    readln(f, n, k);
    for x := 1 to k do
    begin
       readln(f, c, sek[x].i, sek[x].j);
       sek[x].b := 0;
       case c of
        'L': sek[x].k := 1;
        'M': sek[x].k := 2;
        'A': sek[x].k := 3;
        'S': sek[x].k := 4
      end
    end
  end;

begin
  assign (f,'prog.dat');
  reset (f);
  skaityk;
  close (f);
  for kom := 1 to 4 do
    for p := 1 to k do
      begin
        for x := 1 to k do
          begin
            if sek[x].k = kom then
              begin
                i := sek[x].i;
                j := sek[x].j;
                for l := 1 to k do
                  begin
                    if sek[l].b = 0 then
                      if nesikerta then
                         sek[l].b := sek[x].b;
                    if (sek[l].b = sek[x].b) and (l <> x) and (x < l) then
                      if (not nesikerta) then
                         sek[l].b := sek[l].b + 1
                  end
              end
          end
      end;
  Assign (f,'prog.rez');
  Rewrite (f);
  for x := 1 to k do
  begin
    nul := false;
    for l := 1 to k do
      if sek[l].b = x then
      begin
        nul := true;
        writeln(f, l)
      end;
    if nul then writeln(f,'0')
  end;
  close (f)
end.{ M.Bir�i�kos gimnazijos     }
{ 2 GD klas�s mokinio        }
{ Justo Janausko             }
{ XI informatios olimpiados  }
{ III etapo II dalies        }
{ II u�davinio sprendimas    }

{ Apra�ymas
  Komandos turi du parametrus. Jei komanda yra L, mums svarbus
  yra tik antrasis parametras, nes tai yra konstanta, o ne atminties
  l�stel�. Kit� komand� mums svarb�s abu parametrai - i ir j. Taigi,
  imam pirm� komand� ir �dedam � m�s� pirm� blok�. Pasi�ymim imtos
  komandos parametrus ir �i� komand� i�metam i� s�ra�o. Tada imam
  sekan�i� komand� ir �i�rim ar jos svarb�s parametrai jau buvo panaudoti
  kur nors esan�iame bloke. Jei ne - darom t� pat� kaip su anks�iau
  apra�yta komanda. Jei taip, komand� ignoruojam ir imam sekan�i� po
  jos. Taip perrenkam visas komandas. Taip sudarytas pirmasis komand�
  blokas. Antr�j� blok� sudarin�jam lygiai taip pat kaip ir pirm�j�.
  Tol vykdom program�, kol s�ra�e nelieka nei vieno bloko.
}

const
  strIn = 'prog.dat';
  strOut = 'prog.rez';

type
  TCommand = record
    c: char;
    i, j: Integer;
  end;
var
  l, k, bc, last: Integer;
  Arr: array [1..10000] of TCommand;
  Block: array [1..1000] of Integer;

procedure ReadData;
var
  f: Text;
  a: Integer;
begin
  Assign(f, strIn);
  Reset(f);
  ReadLn(f, l, k);
  last := 1;
  for a := 1 to k do
  begin
    Read(f, arr[a].c){, arr[a].i, arr[a].j)};
    Read(f);
    ReadLn(f, arr[a].i, arr[a].j);
  end;
  Close(f);
end;

procedure MakeBlock;
var
  used: array[1..1000] of Boolean;
  a: Integer;
  b: Boolean;
begin
  FillChar(used, SizeOf(used), False);
  bc := 0;
  for a := 1 to k do
  begin
    if arr[a].c <> #0 then
    begin
      if arr[a].c in ['L'] then
        b := not used[arr[a].i]
      else
        b := (not used[arr[a].i]) and (not used[arr[a].j]);
      if b then
      begin
        Inc(bc);
        Block[bc] := a;
        if arr[a].c in ['M', 'S', 'A'] then
          used[arr[a].j] := True;
        arr[a].c := #0;
        used[arr[a].i] := True;
      end;
    end;
  end;
end;

procedure Optimize;
var
  f: Text;
  a: Integer;
begin
  Assign(f, strOut);
  Rewrite(f);
  MakeBlock;
  while bc <> 0 do
  begin
    for a := 1 to bc do
      WriteLn(f, Block[a]);
    WriteLn(f, 0);
    MakeBlock;
  end;
  Close(f);
end;

begin
  ReadData;
  Optimize;
end.var f:text;
BEGIN
assign(f,'prog.rez');
writeln(f,'1');
writeln(f,'2');
writeln(f,'6');
writeln(f,'0');
writeln(f,'3');
writeln(f,'0');
writeln(f,'4');
writeln(f,'5');
writeln(f,'0');
END.