// Donna Gabai, dgabai, P01
// fall09 exam 2
// DFA client
// dependencies: In, State2, StdIn, StdOut, ST

public class DFA2
{
  // initialize global variable
  private State2[] machine;
  private int N;
  
  // DFA constructor
  public DFA2(In in)
  {
    // first entry on input file is how many states
    int N = in.readInt();
    machine = new State2[N];
    
    // make the machine
    for (int i = 0; i < N; i++)
    {
      // one symbol table for each state
      ST<Character, Integer> st = new ST<Character, Integer>();
      String type = in.readString();
      char x;
      do {
        x = in.readString().charAt(0);
        // put it on the state symbol table
        int nextState   = in.readInt();
        st.put(x, nextState);
      }  while (x != '$');
      
      machine[i] = new State2(type, st);
    }
  }
  
  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++) {
      // send the 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)
  {
    // the specific dfa file
    In in = new In(args[0]);
    DFA2 dfa = new DFA2(in);
    
    // print out DFA
    System.out.println(dfa);
    
    // keep processing Strings until get EOF
    // each String considered a separate input
    while (!StdIn.isEmpty())
    {
      String input = StdIn.readString();
      StdOut.println(dfa.run(input));
    }
  }
}