uses
	testlib, SysUtils;
var
	ja, pa, s, nt, i, j, k, st, n: longint;
	z: string;
	next: array [1..10000, '0'..'1'] of longint;
	term: array [1..10000] of boolean;
begin
	ja := ans.readlongint;
	pa := ouf.readlongint;

	if pa < 1 then
		quit(_wa, format('invalid number of states: %d', [pa]));

	if pa > ja then
		quit(_wa, format('expected: %d, found: %d', [ja, pa]));

	s := ouf.readlongint;
	if (s < 1) or (s > pa) then
		quit(_wa, format('invalid starting state: %d', [s]));
	
	nt := ouf.readlongint;
	if (nt < 0) or (nt > pa) then
		quit(_wa, format('invalid number of terminal states: %d', [nt]));

   	for i := 1 to nt do begin
   		k := ouf.readlongint;
   		if (k < 1) or (k > pa) then
   			quit(_wa, format('invalid terminal state: %d', [k]));
   	  	if term[k] then
   			quit(_wa, format('duplicate terminal state: %d', [k]));
   	   	term[k] := true;
   	end;

   	for i := 1 to pa do begin
   		next[i]['0'] := ouf.readlongint;
   		if (next[i]['0'] < 1) or (next[i]['0'] > pa) then
   			quit(_wa, format('invalid transition from %d by 0 to %d', [i, next[i]['0']]));
   		next[i]['1'] := ouf.readlongint;
   		if (next[i]['1'] < 1) or (next[i]['1'] > pa) then
   			quit(_wa, format('invalid transition from %d by 1 to %d', [i, next[i]['1']]));
   	end;

	n := inf.readlongint;
	for i := 0 to n do begin
		for j := 1 to 1 shl i do begin
			z := inf.readword(blanks, blanks);
			st := s;
			for k := 2 to length(z) do begin
				st := next[st][z[k]];
			end;
			if (z[1] = '+') xor (term[st]) then
				quit(_wa, 'condition ' + z + ' is not satisfied');
		end;
	end;

	if (pa < ja) then
		quit(_fail, format('expected: %d, found: %d', [ja, pa]));

	quit(_ok, format('n = %d, states = %d', [n, pa]));
end.