import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main
{
	public static ArrayList<String> ruleList = new ArrayList<String>();

	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);

		for(int i = 0; i < 3; i++)
		{
			ruleList.add(scan.nextLine());
		}
		String instruction = scan.nextLine();

		String[] tokens = instruction.split(" ");

		String input = tokens[1];
		for(String s: findAllPossibilities(tokens[1] + ",", ruleList, Integer.parseInt(tokens[0])))
		{
			input = tokens[1];
			String[] split = s.split(",");

			if(split[0].equals(tokens[2]))
			{
				String[] steps = split[1].split(":");

				for(int i = 0; i < steps.length; i+= 2)
				{
					input = useRule(input, ruleList.get(Integer.parseInt(steps[i])), Integer.parseInt(steps[i+1]));
					System.out.println((Integer.parseInt(steps[i]) + 1) + " " + (Integer.parseInt(steps[i+1]) + 1) + " " + input);
				}

				System.exit(0);
			}
		}


	}

	public static ArrayList<String> findPossibilities(String input, ArrayList<String> rules)
	{
		ArrayList<String> possibilities = new ArrayList<String>();

		for(String s: rules)
		{
			String[] tokens = s.split(" ");

			if(input.contains(tokens[0]))
			{
				for(int i : getIndexes(input, tokens[0]))
				{
					possibilities.add(rules.indexOf(s) + "," + i);
				}
			}
		}

		return possibilities;
	}

	public static ArrayList<Integer> getIndexes(String input, String test)
	{
		ArrayList<Integer> indexes = new ArrayList<Integer>();

		int startIndex = 0;

		for(int i = 0; i < input.length(); i++)
		{
			if(input.indexOf(test, startIndex) != -1)
			{
				indexes.add(input.indexOf(test, startIndex));
				startIndex = input.indexOf(test, startIndex) + 1;
			}
		}

		return indexes;
	}

	public static String useRule(String input, String rule, int index)
	{
		String[] tokens = rule.split(" ");

		String firstpart = input.substring(0, index);
		String secondpart = input.substring(index + tokens[0].length());
		return firstpart + tokens[1] + secondpart;
	}

	public static ArrayList<String> findAllPossibilities(String input, ArrayList<String> rules, int depth)
	{
		ArrayList<String> allPossibilities = new ArrayList<String>();
		ArrayList<String> newItems = new ArrayList<String>();
		ArrayList<String> itemsToTest = new ArrayList<String>();

		itemsToTest.add(input);

		for(int i = 0; i < depth; i++)
		{
			for(String test: itemsToTest)
			{
				for(String s: findPossibilities(test, rules))
				{
					//System.out.println(itemsToTest);
					//System.out.println(findPossibilities(test, rules) + " possibltiltity");

					String[] tokens = s.split(",");
					String[] splitTest = test.split(",");
					//System.out.println(test + " " + ruleList.get(Integer.parseInt(tokens[0])) + " " + Integer.parseInt(tokens[1]));

					if(i > 0)
					{
						newItems.add(useRule(splitTest[0], ruleList.get(Integer.parseInt(tokens[0])), Integer.parseInt(tokens[1])) + "," + splitTest[1] + tokens[0] + ":" + tokens[1] + ":");
					}
					else
					{
						newItems.add(useRule(splitTest[0], ruleList.get(Integer.parseInt(tokens[0])), Integer.parseInt(tokens[1])) + "," + tokens[0] + ":" + tokens[1] + ":");
					}
				}
			}

			itemsToTest.clear();
			itemsToTest.addAll(newItems);
			newItems.clear();
		}

		return itemsToTest;
	}
}