{ 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}