{ CEOI 2003 - M¸nster, Germany - Task: Pearls. Sample Solution }
{ Author of this program: Tobias Thierer <ceoi@tobias-thierer.de> }
program pearls;

uses pearls_lib;

const inname     = 'pearls.in';
      MAX_PEARLS = 1000;
      MAX_DWARFS = 1000;
      MAX_LIST_LENGTH = 20;
      assertions = true;

type dwarfsRange = 1..MAX_DWARFS;
     pearlColor = (black, white);

var numPearls  : Integer; { length of the necklace, 1 <= numPearls <= 1000 }
    numDwarfs  : Integer;
    firstDwarf : Integer;
    necklace   : array[1..MAX_PEARLS] of pearlColor;
    listLength : array[pearlColor, dwarfsRange] of Integer; { lengths of white and black lists }
    list       : array[pearlColor, dwarfsRange, 1..MAX_LIST_LENGTH] of Integer;
    isGreenDwarf : array[dwarfsRange] of Boolean;

    { canWin[i,j]: will the folk of dwarf i get the diamond if he gets the necklace in step #j? }
    canWin     : array[dwarfsRange, 1..MAX_PEARLS] of Boolean;
    bestMove   : array[dwarfsRange, 1..MAX_PEARLS] of Integer; { best dwarf to hand the necklace to }

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

procedure assert(b:Boolean; msg:String);
begin
  if assertions and (not b) then begin
    writeln('ERROR: Assertion failed: ',msg);
    halt(255);
  end;
end;

procedure readData;
var actPearl, actDwarf, i: Integer;
    ch    : Char;
    color : pearlColor;
    inf   : text;
begin
  assign(inf, inname);
  reset(inf);
  readln(inf, numPearls, numDwarfs, firstDwarf);
  for actPearl:=1 to numPearls-1 do begin
    read(inf, ch);
    assert((ch = 'B') or (ch='W'), 'pearl neither [B]lack nor [W]hite.');
    if (ch='B') then necklace[actPearl] := black else necklace[actPearl] := white;
  end;
  readln(inf, ch); { 'D', diamond }
  assert(ch='D', 'diamond expected at end of necklace, found ' + ch);
  for actDwarf:=1 to numDwarfs do begin
    read(inf, i);
    isGreenDwarf[actDwarf] := (i=0);
    for color:=black to white do begin
        read(inf, listLength[color,actDwarf]);
        assert(listLength[color, actDwarf] <= MAX_LIST_LENGTH, 'Black or white list too long.');
        for i:=1 to listLength[color,actDwarf] do read(inf, list[color,actDwarf,i]);
    end;
    readln(inf);
  end;
  close(inf);
end;


procedure checkWins;
var actDwarf, nextDwarf : Integer;
    necklaceIdx, i      : Integer;
    actPearlColor       : pearlColor;
    sameTribe : Boolean;
begin
  for actDwarf:=1 to numDwarfs do begin
    canWin[actDwarf, numPearls] := true;
    bestMove[actDwarf, numPearls] := -1; { doesn't really matter, never read except in an assertion}
  end;
  for necklaceIdx := numPearls-1 downto 1 do begin
    actPearlColor := necklace[necklaceIdx];
    for actDwarf := 1 to numDwarfs do begin
      canWin[actDwarf, necklaceIdx] := false;
      bestMove[actDwarf, necklaceIdx] := list[actPearlColor, actDwarf, 1];

      for i := 1 to listLength[actPearlColor, actDwarf] do begin
        nextDwarf := list[actPearlColor, actDwarf, i];
        sameTribe := (isGreenDwarf[actDwarf] = isGreenDwarf[nextDwarf]);

        if (   (sameTribe and (canWin[nextDwarf, necklaceIdx+1]))
            or ((not sameTribe) and (not canWin[nextDwarf, necklaceIdx+1])))
        then begin
          canWin[actDwarf, necklaceIdx] := true;
          bestMove[actDwarf, necklaceIdx] := nextDwarf;
          break;
        end;
      end;
    end;
  end;
end;

procedure play;
var pearlNum: Integer;
    currDwarf : Integer;
begin
  currDwarf := firstDwarf;
  for pearlNum:=1 to numPearls - 1 do begin
    if isGreenDwarf[currDwarf] then begin
      currDwarf := bestMove[currDwarf, pearlNum];
      assert((currDwarf >= 1) and (currDwarf <= numDwarfs),
             ' illegal dwarf number generated.');
      setNext(currDwarf);
    end
    else currDwarf := getNext;
  end;
  finish;
end;

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

begin { main }
  readData;
  checkWins;
  assert(canWin[firstDwarf,1] = isGreenDwarf[firstDwarf],'I can''t win!');
  play;
end.  { main }