{ U‘davinio autorius: Irus Grinis, Vilniaus "Ź‘uolyno" v.m. informatikos
  mokytojas.
  Sprendim… bei testus pareng‚ Irus Grinis.

   Sprendimo id‚ja paprasta. Naudojame  klasikinŤ d‚kl….Patalpiname paskutinŤ
  sakinŤ Ť d‚kl…. Paskutiniame sakinyje  mes turime gauti skai‡i— N. Iž ‡ia
  lengvai  galima  surasti  kintamojo  sakinio  dežin‚je   reikžmŠ  (tai
  atlieka   funkcija   desine). Nevisada kintamojo reikžm‚  egzistuoja:
  pavyzd‘iui, kai k turi b–ti  7, o sakinys yra k:=l*3, tai kitamajam l reik-
  žm‚s neegzistuoja.Dar  vienas pavyzdys : sakiniui k:=l+3, kai k turi b–ti 2,
  kintamasis l irgi neturi reikžm‚s.Tuo  atv‚ju, kai reikžm‚ dežin‚je egzis-
  tuoja, judame Ť ôvirž—ő ir mieginame surasti sakinŤ, kurio kair‚je yra tas
  pats kintamasis,kuris buvo priež tai dežin‚je pus‚je ir kurio kintamasis
  dežin‚je turi reikžmŠ.Galimi 3 atv‚jai :

              1 SakinŤ suradome ir kintamojo dežin‚je reikžm‚ nelygi 1;
              2 SakinŤ suradome ir kintamojo dežin‚je reikžm‚ lygi 1;
              3 Sakinio nesuradome.

  Pirmame atv‚jyje   padedame  sakinŤ Ť d‚kl… ir mieginame rasti kit… atitin-
  kam… sakinŤ, kurio numeris ma‘esnis negu dabar surastas.Antru atv‚ju spren-
  dinys jau gautas : reikalingi  sakiniai  yra   patalpinti d‚kle.Tre‡iu atv‚ju
  ižimame iž d‚klo sakinŤ ir mieginame surasti kit… tinkam… sakinŤ priež tai
  buvusiam sakiniui.  Jeigu ka‘kuriame   ‘ingsnyje  d‚klas tampa  tuž‡ias,tai
  reikalingos sakini— sekos n‚ra.

}




type Tsakinys=record
              kaire : 1..26;
              desine: 1..26;
              zenklas:boolean;
              skaicius:integer;
             end;

type Tzingsnis=record
              sak_nr:integer;
              reiksme    :integer;
              nuo        :integer;
             end;

const MAKS_SAKINIU_KIEKIS=22;

   var   sakiniai : array[1..MAKS_SAKINIU_KIEKIS] of Tsakinys;
         sprendimas :array[0..MAKS_SAKINIU_KIEKIS] of Tzingsnis;
         N : integer;

         sak_kiekis:integer;
         inf_kiekis:integer;
         kartu:longint;

{--------------------------------------}
procedure skaityti_duomenis;    {  Nuskaitome pradinius duomenis ir pildome
                                   "reikalingas" strukt–ras }
  var f :text;
      s:string;
      Nr,k,i:integer;
  begin
     assign(f,'sakiniai.dat');
     reset(f);
     readln(f,N);
     readln(f,sak_kiekis);
     for Nr:=1 to sak_kiekis do
     begin
      readln(f,s);
      sakiniai[Nr].desine:=1+ord(s[4])-ord('a');
      sakiniai[Nr].kaire:=1+ord(s[1])-ord('a');
      sakiniai[Nr].zenklas:=(s[5]='*');
      i:=6;
      k:=0;
      while s[i]<>';' do begin k:=k*10+ord(s[i])-ord('0');i:=i+1;end;
      sakiniai[Nr].skaicius:=k;
     end;
     close(f);
  end;
{--------------------------------------}

function  rasti:boolean;   {  Funkcija, kuri sprend‘ia u‘davinŤ  }

  {--------------------------------------}

  function desine(kaire,sak_numeris:integer):integer;{Randa kintamojo sakinio
                                                      dežin‚je reikžme,kai
                                                      duota reikžm‚ kair‚je}
   begin
    if (sak_numeris<0) or ((sak_numeris=0) and (kaire<>1) )
      then desine:=-1
      else if sak_numeris=0
          then desine:=1
          else if sakiniai[sak_numeris].zenklas
            then
               begin
                if (sakiniai[sak_numeris].skaicius=0) and (kaire=0)
                          then begin desine:=1;exit;end;
                if (sakiniai[sak_numeris].skaicius=0) and (kaire<>0)
                          then begin desine:=-1;exit; end;

                if (kaire mod sakiniai[sak_numeris].skaicius=0)
                 then begin desine:=kaire div sakiniai[sak_numeris].skaicius;exit; end
                 else begin desine:=-1;exit;end;
               end
          else desine:=kaire-sakiniai[sak_numeris].skaicius;

end;

  {--------------------------------------}

  function rasti_sakini(ieskancio_nr,     {Randa "tinkam…" sakinŤ}
                      ieskancio_reiksme,
                      ieskoti_nuo:integer;
                      var rasto_reiksme:integer):integer;


 var k,ieskancio_desine,ra_reiksme:integer;

 begin
  if ieskoti_nuo=0
    then k:=-1
    else
      begin
         k:=ieskoti_nuo-1;
         ieskancio_desine:=desine(ieskancio_reiksme,ieskancio_nr);
         rasto_reiksme:=ieskancio_desine;
         if (ieskancio_desine<0)
           then begin rasti_sakini:=-1;exit; end;
         while (true) do
         begin

          ra_reiksme:=desine(ieskancio_desine,k);

          if (ra_reiksme>=0)
               then if (k=0)
                    then break
                    else if (sakiniai[k].kaire=sakiniai[ieskancio_nr].desine)
                         then break;


          k:=k-1;

          if (k<0) then break;

         end;
      end;
  rasti_sakini:=k;
 end;

  {--------------------------------------}

 var i,step,des,kaire,sak:integer;
 var rasto_nr,rasto_reiksme:integer;

begin  { rasti }

  for i:=0 to MAKS_SAKINIU_KIEKIS  do
  begin
    sprendimas[i].sak_nr:=0;
    sprendimas[i].reiksme:=0;
    sprendimas[i].nuo:=0;
  end;


  step:=1;
  sprendimas[step].sak_nr:=sak_kiekis;
  sprendimas[step].reiksme:=N;
  sprendimas[step].nuo:=sak_kiekis;

  while (true)  do
     begin
         rasto_nr:=rasti_sakini(sprendimas[step].sak_nr,
                               sprendimas[step].reiksme,
                               sprendimas[step].nuo,
                               rasto_reiksme);

         if ( rasto_nr > 0 )
                  then begin
                        sprendimas[step].nuo:=rasto_nr;
                        inc(step);
                        sprendimas[step].nuo:=rasto_nr;
                        sprendimas[step].reiksme:=rasto_reiksme;
                        sprendimas[step].sak_nr:=rasto_nr;
                       end
                   else if ( rasto_nr=0 )
                   then begin rasti:=true;exit;end
                   else begin
                         sprendimas[step].nuo:=0;
                         sprendimas[step].reiksme:=0;
                         sprendimas[step].sak_nr:=0;
                         dec(step);


                        end;

       if step=0 then begin rasti:=false;exit;end
     end;

end;  {rasti}

{--------------------------------------}

   var li:longint;
       h,m,s,ss:word;
       rez:text;

   begin { program }
    skaityti_duomenis;
    assign(rez,'sakiniai.ats');
    rewrite(rez);
    writeln(m,' ',s,' ',ss);
    if rasti then
              begin
               writeln(rez,'TAIP');
               for li:=MAKS_SAKINIU_KIEKIS downto 0 do
                 if ( sprendimas[li].sak_nr <> 0 )
                     then writeln( rez,sprendimas[li].sak_nr);
              end
             else writeln(rez,'NE');
     writeln(m,' ',s,' ',ss);

    close(rez);
  end.  {program}