import java.util.Scanner;
import java.io.PrintStream;
import java.util.Vector;
import java.lang.String;

public class TM {
    final int numStates; // number of states in the state set
    final int tapeAlphaSize; // number of characters in the tape alphabet
    final int inputAlphaSize; // number of characters in the input alphabet
    final String tapeAlpha;

    int[][] nextState; // these three arrays are used to store the transition function
    int[][] charToWrite;
    boolean[][] moveLeft;

    public TM(Scanner in) {
	// Creates a Turing machine by reading it (in YUTMDF) from in.

	numStates = in.nextInt();
	assert numStates >= 3;
	tapeAlphaSize = in.nextInt();
	inputAlphaSize = in.nextInt();
	assert inputAlphaSize >= 1 && tapeAlphaSize >= inputAlphaSize + 2;

	tapeAlpha = in.next() + "_>";
	assert tapeAlpha.length() == tapeAlphaSize;
	for (int i = 0; i < tapeAlphaSize; i++) 
	    // check that each character only appears once in tapeAlpha
	    assert tapeAlpha.lastIndexOf(tapeAlpha.charAt(i)) == i;
	
	nextState =    new int[numStates-2][tapeAlphaSize];
	charToWrite =  new int[numStates-2][tapeAlphaSize];
	moveLeft = new boolean[numStates-2][tapeAlphaSize];

	boolean[][] done = new boolean[numStates-2][tapeAlphaSize]; 
	// temporary variable used to make sure that each transition is 
	// only defined once in the input

	for (int i = 0; i < numStates-2; i++) {
	    for (int j = 0; j < tapeAlphaSize; j++) {
		// set default values
		nextState[i][j] = i;
		charToWrite[i][j] = j;
		moveLeft[i][j] = false;
		done[i][j] = false;
	    }
	}
	
	// Read in transitions
	int numTransitions = in.nextInt();
	for (int k = 0; k < numTransitions; k++) {
	    int i = in.nextInt();
	    assert i >= 0 && i < numStates - 2;
	    int j = tapeAlpha.indexOf(in.next());
	    assert j >= 0 && j < tapeAlphaSize; 
	    assert !done[i][j];
	    done[i][j] = true;

	    nextState [i][j] = in.nextInt();
	    assert nextState[i][j] >= 0 && nextState[i][j] < numStates;
	    String character = in.next();
	    charToWrite[i][j] = tapeAlpha.indexOf(character);
	    assert charToWrite[i][j] >= 0 && charToWrite[i][j] < tapeAlphaSize;
	    String direction = in.next();
	    assert direction.equals("L") || direction.equals("R");
	    moveLeft[i][j] = (direction.equals("L"));

	    if (j == leftEnd()) {
		// check that left-end marker is handled correctly
		assert !moveLeft[i][j] && charToWrite[i][j] == leftEnd();
	    }
	}
    }

    private final int blank() { return tapeAlphaSize - 2; }
    private final int leftEnd() { return tapeAlphaSize - 1; } 
    private final int acceptState() { return numStates - 2; }
    private final int rejectState() { return numStates - 1; }

    private void printConfig(PrintStream out, int stepCounter, Vector<Integer> tape, 
			     int state, int pos) {
	// Prints a configuration of the machine.

	out.print("Configuration after " + stepCounter + " steps: ");
	for (int i = 0; i < tape.size(); i++) {
	    if (pos==i) out.print("q" + state + " ");
	    out.print(tapeAlpha.charAt(tape.get(i)) + " ");
	}
	if (pos==tape.size()) out.print("q" + state + " ");
	out.println();
    }

    public void run(Scanner in, PrintStream out, int numSteps, boolean trace) {
	// Reads a string from in and runs the Turing machine on it.
	// Format for input string:  sequence of integers separated by spaces
	// giving each character, terminated by -1.
    
	int state=0; // start in state 0
	int pos = 1; // head position
	Vector<Integer> tape = new Vector<Integer>(10000,0); // tape contents

	// Initialize tape with input string
	tape.add(leftEnd());
	int c = tapeAlpha.indexOf(in.next());
	while (c != blank()) {
	    assert c >= 0 && c < inputAlphaSize;
	    tape.add(c);
	    c = tapeAlpha.indexOf(in.next());
	}

	// Run the machine for numSteps steps
	int stepCounter = 0;
	if (trace) printConfig(out, stepCounter, tape, state, pos);
	while (state < acceptState() && stepCounter++ <= numSteps) { 
	    // simulate one step of the Turing machine
	    if (pos == tape.size()) // extend tape if TM has run beyond right end
		tape.add(blank());
	    int oldChar = tape.get(pos);
	    tape.set(pos, charToWrite[state][oldChar]);
	    pos = (moveLeft[state][oldChar]) ? pos - 1 : pos + 1;
	    state = nextState[state][oldChar];
	    if (trace) printConfig(out, stepCounter, tape, state, pos);
	}
	if (state == acceptState())
	    out.println("Turing machine has accepted after " + stepCounter + " steps.");
	else if (state == rejectState())
	    out.println("Turing machine has rejected after " + stepCounter + " steps.");
	else
	    out.println("Turing machine ran for " + stepCounter + " steps without halting.");
    }
 
    int run(String input, PrintStream out, int numSteps, boolean trace) {
	// Runs the Turing machine on input.
    
	int state = 0; // start in state 0
	int pos = 1; // head position
	Vector<Integer> tape = new Vector<Integer>(10000,0); // tape contents

	// Initialize tape with input string
	tape.add(leftEnd());
	for (int i = 0; i < input.length(); i++) {
	    int c = tapeAlpha.indexOf(input.charAt(i));
	    assert c >= 0 && c < inputAlphaSize;
	    tape.add(c);
	}

	if (trace) out.println("TESTING " + input);


	// Run the machine for numSteps steps
	int stepCounter = 0;
	if (trace) printConfig(out, stepCounter, tape, state, pos);
	while (state < acceptState() && stepCounter++ <= numSteps) { 
	    // simulate one step of the Turing machine
	    if (pos == tape.size()) // extend tape if TM has run beyond right end
		tape.add(blank());
	    int oldChar = tape.get(pos);
	    tape.set(pos, charToWrite[state][oldChar]);
	    pos = (moveLeft[state][oldChar]) ? pos - 1 : pos + 1;
	    state = nextState[state][oldChar];
	    if (trace) printConfig(out, stepCounter, tape, state, pos);
	}
	if (state == acceptState()) {
	    if (trace) out.println("Turing machine has accepted after " + stepCounter + " steps.");
	    return 1; }
	else if (state == rejectState()) {
	    if (trace) out.println("Turing machine has rejected after " + stepCounter + " steps.");
	    return 0; }
	else {
	    if (trace) out.println("Turing machine ran for " + stepCounter + " steps without halting.");
	    return -1; }
    }
 
    public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	PrintStream out = System.out;
	
	String allZeroes = "000000000000000000000000";
	String allOnes = "11111111111111111111111";
	TM machine = new TM(in);

	String testString = "";
	int numZeroes = 0;
	int numOnes = 0;
	int score = 0;

	while (testString.length() < 16) {
	    boolean expectedOutput = (numZeroes <= 2 * numOnes);

	    int output = machine.run(testString, out, 10000, false);
	    if ((expectedOutput && output == 1) || (!expectedOutput && output == 0)) {
		score++;
		out.println(testString + " correct output");
	    } else if (output == -1)
		out.println(testString + " did not terminate");
	    else
		out.println(testString + " incorrect output");

	    // increment test String
	    int pos = testString.lastIndexOf('0');
	    if (pos == -1) {
		testString = allZeroes.substring(0, 1 + testString.length());
		numZeroes = testString.length();
		numOnes = 0;
	    } else {
		testString = testString.substring(0, pos) + "1" + 
		    allZeroes.substring(1,testString.length()-pos); 
		numZeroes = numZeroes + testString.length() - pos - 2;
		numOnes = testString.length() - numZeroes;
	    }
	}
	out.println("Your Turing machine worked for " + score + " of the 65535 test strings.");
	int grade;
        if (score <= 32768) grade = 0;
	else grade = 100 * (score - 32768) / 32767;
	if (score != 65535 && grade > 90) grade = 90;
	out.println("Grade on assignment is " + grade + "%.");
    }	

}