// Fall09 Exam 2 Programming Exam  
 // DFA class to read in a description of a DFA machine and 
 // simulate the operation of the DFA on input strings   
 // dependencies: State, StdIn, StdOut, In  

public class  DFA {
    private  State [] machine;
    private int N;

   public DFA(In in){

      int N = in.readInt();
      machine = new State[N];

      for (int i = 0; i <  N; i++)
      {
         String type = in.readString();
	 int next0   = in.readInt();
	 int next1   = in.readInt();
         machine[i] = new  State (type, next0, next1);
      }
   }

   public String run( String input)
   {
     int count = input.length();
     int stateNum = 0;   // which state are we in? start at 0
     // input String needs to be processed
     // one char at a time
     for (int i = 0; i < count; i++) {
        // determine the next state from the current char
        stateNum = machine[stateNum].next(input.charAt(i));
     }
    
     // return accept or reject
     return machine[stateNum].type();
   }

   // debugging aid
   public String toString()
   {
      String s = "";
      for (int j = 0; j < machine.length; j++)
         s += machine[j] .type() + " " + machine[j] .next('0') + " " + 
	      machine[j] .next('1');

      s += '\n';
      return s;
   }

   public static void main(String[]  args)
   {
      In in = new In(args[0] );
      DFA dfa = new  DFA (in);

      // print out DFA
      System.out.println(dfa);
      while (!StdIn.isEmpty())
      {
         String input = StdIn.readString();
         StdOut.println(dfa.run(input));
      }
    }
}