import java.util.*;
import java.io.*;

// represents a state in a finite state machine
class State {

	public HashMap<Character,Integer> transitions;
	public boolean accepting;
	public int stateNumber;
	
	public State() {
		transitions = new HashMap<Character,Integer>();
		accepting = false;
		stateNumber = -1; // this is changed later
	}
}

class FSM {
	
	// FIXME: this method might not handle blank lines well
	public static HashMap<Integer,State> buildMachine(String machineFile) throws Exception {
		HashMap<Integer,State> machine = new HashMap<Integer,State>();
		Scanner machineFileReader = new Scanner(new File(machineFile));
		// go line by line and read the state
		while (machineFileReader.hasNextLine()){ 
			String theLine = machineFileReader.nextLine();
			// tokenize the line
			StringTokenizer theLineTokenizer = new StringTokenizer(theLine);
			// the first token is always the token number
			State s = new State();
			int newIndex = Integer.valueOf(theLineTokenizer.nextToken());
			machine.put(newIndex,s);
			s.stateNumber = newIndex;
			
			// read each next token on the line
			while (theLineTokenizer.hasMoreTokens()){
				String tmpToken = theLineTokenizer.nextToken();
				if (tmpToken.equals("X")) {
					s.accepting = true;					
				} else {
					// the next token is a transition, split it up based on 
					StringTokenizer st = new StringTokenizer(tmpToken,":");
					int index = Integer.valueOf(st.nextToken());
					String filter = st.nextToken();
					if (filter.equals("A"))
						filter = "abcdefghijklmnopqrstuvwxyz";
					if (filter.equals("D"))
						filter = "1234567890";
					if (filter.equals("N"))
						filter = "123456789";
					if (filter.equals("S"))
						filter = "~!@#%^&*()-+{}.,";
					// for each character in the filter, add a transition
					for (int j = 0; j < filter.length();j++)
						s.transitions.put(filter.charAt(j),index);
				}
			}
		}	
		return machine;
	}

	public static boolean executeMachine(HashMap<Integer,State> machine, String input) {
		State currentState = (State) machine.get(1);
		State defaultRejection = new State(); // for those times when nothing else matches, go to default rejection
		for (int i = 0; i < input.length(); i++) {
			//System.out.println("Current state is: " + currentState.stateNumber);
			char c = input.charAt(i);
			//System.out.println("Current input is: " + c);
			if (currentState.transitions.containsKey(c)) {
				currentState = machine.get(currentState.transitions.get(c));
				//System.out.println("Moving to state " + currentState.stateNumber);
			} else {
				currentState = defaultRejection;
				break; // I realize it's not good form but it works
			}
		}
		return currentState.accepting;
	}

	public static void main(String [] args) throws Exception {
		// read each finite state machine into an Array List
		ArrayList<HashMap<Integer,State> > machines = new ArrayList<HashMap<Integer,State> >(); // so ugly
		for (int i =0; i<args.length-1;i++) 
			machines.add(buildMachine(args[i]));

		// get the input strings
		String stringsFile = args[args.length-1];
		Scanner stringReader = new Scanner(new File(stringsFile));

		while (stringReader.hasNextLine()) {
			String line = stringReader.nextLine();
			// for each line, run it through a machine
			int m = 1;
			for (HashMap<Integer,State> machine : machines) {
				System.out.println("*********************");
				System.out.println("* MACHINE " + (m++));
				System.out.println("*********************");
				System.out.println("INPUT: " + line);
				String accepted = (executeMachine(machine,line)) ? "accepted" : "not accepted";
				System.out.println(accepted);
			}
		}
	}
}