import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Closure1 {
	static Scanner input;
	static Stack<Production> grammar;
	static Stack<Configuration> question;
	static FirstSet firstSet;
	static FileWriter outputFile;

	public static void main(String[] args) {
		grammar = new Stack<Production>();
		question = new Stack<Configuration>();
		input("input.txt");

		try {
			outputFile = new FileWriter("output.txt");
		} catch (IOException e) {
			e.printStackTrace();
		}

		// showGrammar();

		firstSet = new FirstSet(grammar);
		// firstSet.showFirstSet();

		// System.out.println("Question:");
		// showConfiguration(question);
		// System.out.println();

		solveQuestion();
		try {
			outputFile.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static void solveQuestion() {
		Stack<Configuration> answer = new Stack<Configuration>();
		for (int i = 0; i < question.size(); i++) {
			answer.push(question.get(i).clone());
			doClosure1(answer);
			//showConfiguration(answer);
			mergeAnswer(answer);
			writeAnswer(answer);
			showConfiguration(answer);
			System.out.println("#");
			answer.clear();
		}
	}

	private static void writeAnswer(Stack<Configuration> answer) {
		String content = "";
		for (int i = 0; i < answer.size(); i++) {
			content += answer.get(i).from + "->";
			// show String to with *
			for (int j = 0; j < answer.get(i).to.length(); j++) {
				if (answer.get(i).point == j) {
					content += '*';
				}
				content += answer.get(i).to.charAt(j);
			}

			if (answer.get(i).point == answer.get(i).to.length()) {
				content += '*';
			}

			// show lookahead
			content += " {" + answer.get(i).lookahead.charAt(0);
			for (int j = 1; j < answer.get(i).lookahead.length(); j++) {
				content += "," + answer.get(i).lookahead.charAt(j);
			}
			content += "}\r\n";
		}
		content += "#\r\n";
		try {
			outputFile.write(content);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private static void mergeAnswer(Stack<Configuration> answer) {
		for (int i = 0; i < answer.size(); i++) {
			for (int j = 0; j < i; j++) {
				if (hasSameProductionWithStar(answer, i, j)) {
					mergeLookahead(answer, i, j);
					answer.remove(i);
					i--;
					break;
				}
			}
		}
	}

	private static void mergeLookahead(Stack<Configuration> answer, int i, int j) {
		// union i's lookahead into j's lookahead
		String ilookahead = answer.get(i).lookahead;
		String jlookahead = answer.get(j).lookahead;
		jlookahead = union(jlookahead, ilookahead);
		answer.get(j).lookahead = jlookahead;
	}

	private static String union(String alk, String blk) {
		// union into alk
		for (int i = 0; i < blk.length(); i++) {
			char c = blk.charAt(i);
			if (alk.indexOf(c) == -1) {
				alk = alk + c;
			}
		}
		char[] array = alk.toCharArray();
		Arrays.sort(array);
		alk = String.valueOf(array);
		return alk;
	}

	private static boolean hasSameProductionWithStar(
			Stack<Configuration> answer, int i, int j) {
		char ifrom = answer.get(i).from;
		String ito = answer.get(i).to;
		int ipoint = answer.get(i).point;

		char jfrom = answer.get(j).from;
		String jto = answer.get(j).to;
		int jpoint = answer.get(j).point;

		if (ifrom == jfrom && ito.equals(jto) && ipoint == jpoint) {
			return true;
		} else {
			return false;
		}
	}

	private static void doClosure1(Stack<Configuration> answer) {
		for (int i = 0; i < answer.size(); i++) {
			Configuration conf = answer.get(i);

			if (conf.point < conf.to.length() - 1) {// before S->A*$
				char symbol = conf.to.charAt(conf.point);
				if (!isTerminal(symbol)) {

					// make lookahead
					String afterpoint = conf.to.substring(conf.point + 1);
					String lookahead = firstSet.getFirstSet(afterpoint);
					//System.out.println(i+","+afterpoint + "," + lookahead);
					if (lookahead.indexOf('l') != -1) {
						// remove lemda union conf.lookahead;
						int index = lookahead.indexOf('l');
						lookahead = lookahead.substring(0, index)
								+ lookahead.substring(index + 1);
						lookahead = union(lookahead, conf.lookahead);

					}
					char[] array = lookahead.toCharArray();
					Arrays.sort(array);
					lookahead = String.valueOf(array);
					//System.out.println(lookahead);

					// find productions start with the symbol
					for (int j = 0; j < grammar.size(); j++) {
						Production p = grammar.get(j);
						if (p.from == symbol) {
							Configuration c = new Configuration(p.from, p.to, 0);
							c.lookahead = lookahead;
							// test if the configuration is exist?
							if (!answerExist(answer, c)) {
								answer.push(c);
							}
						}
					}
				}

			} else if (conf.point == conf.to.length() - 1) {
				// the point is at the end. eg.S->A*$ {l}
				char symbol = conf.to.charAt(conf.point);
				if (!isTerminal(symbol)) {
					// make lookahead
					String lookahead = conf.lookahead;

					// find productions start with the symbol
					for (int j = 0; j < grammar.size(); j++) {
						Production p = grammar.get(j);
						if (p.from == symbol) {
							Configuration c = new Configuration(p.from, p.to, 0);
							c.lookahead = lookahead;
							// test if the configuration is exist?
							if (!answerExist(answer, c)) {
								answer.push(c);
							}
						}
					}

				}
			}

		}
	}

	private static boolean answerExist(Stack<Configuration> answer,
			Configuration c) {
		for (int i = 0; i < answer.size(); i++) {
			Configuration ac = answer.get(i);
			if (ac.from == c.from && ac.to.equals(c.to) && ac.point == c.point
					&& ac.lookahead.equals(c.lookahead)) {
				return true;
			}
		}
		return false;
	}

	private static boolean isTerminal(char symbol) {
		return !Character.isUpperCase(symbol);
	}

	private static void showConfiguration(Stack<Configuration> cfs) {
		for (int i = 0; i < cfs.size(); i++) {
			System.out.print(cfs.get(i).from + "->");
			// show String to with *
			for (int j = 0; j < cfs.get(i).to.length(); j++) {
				if (cfs.get(i).point == j) {
					System.out.print('*');
				}
				System.out.print(cfs.get(i).to.charAt(j));
			}

			if (cfs.get(i).point == cfs.get(i).to.length()) {
				System.out.print('*');
			}

			// show lookahead
			System.out.print(" {" + cfs.get(i).lookahead.charAt(0));
			for (int j = 1; j < cfs.get(i).lookahead.length(); j++) {
				System.out.print("," + cfs.get(i).lookahead.charAt(j));
			}
			System.out.print("}\n");
		}
	}

	private static void showGrammar() {
		System.out.println("Grammar:");
		for (int i = 0; i < grammar.size(); i++) {
			System.out.println(grammar.get(i).from + "->" + grammar.get(i).to);
		}
		System.out.println();
	}

	private static void input(String path) {
		try {
			input = new Scanner(new File(path));
			int p_size = input.nextInt();
			input.nextLine();
			for (int i = 0; i < p_size; i++) {
				String line = input.nextLine();
				Production p = new Production(line.charAt(0), line.substring(3));
				grammar.push(p);
			}
			int q_size = input.nextInt();
			input.nextLine();
			for (int i = 0; i < q_size; i++) {
				String line = input.nextLine();
				char from = line.charAt(0);
				int point = line.indexOf('*');
				line = line.substring(0, point) + line.substring(point + 1);
				point = point - 3;

				int p_end = line.indexOf(' ');
				String to = line.substring(3, p_end);

				Configuration c = new Configuration(from, to, point);
				int lk = p_end + 2;
				while (lk < line.length()) {
					c.unionLookahead(line.charAt(lk));
					lk = lk + 2;
				}
				c.sortLookahead();
				question.push(c);
			}

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

}

class Production {
	char from;
	String to;

	public Production(char from, String to) {
		this.from = from;
		this.to = to;
	}
}

class Configuration extends Production {
	int point;
	String lookahead;

	public Configuration(char from, String to, int point) {
		super(from, to);
		this.point = point;
		lookahead = "";
	}

	public void sortLookahead() {
		char[] s = lookahead.toCharArray();
		Arrays.sort(s);
		lookahead = String.valueOf(s);
	}

	public void unionLookahead(char c) {
		if (lookahead.indexOf(c) == -1) {
			lookahead = lookahead + c;
			sortLookahead();
		}
	}

	public Configuration clone() {
		Configuration output = new Configuration(from, to, point);
		output.lookahead = lookahead;
		return output;
	}
}

class FirstSet {
	Stack<Production> grammar;
	char[] symbol;
	String sets[];

	public FirstSet(Stack<Production> grammar) {
		this.grammar = grammar;

		// initial storage
		getAllSymbol();
		sets = new String[symbol.length];
		for (int i = 0; i < sets.length; i++) {
			sets[i] = "";
		}

		// set terminal
		for (int i = 0; i < symbol.length; i++) {
			if (isTerminal(symbol[i])) {
				union(symbol[i], symbol[i]);
			}
		}

		// reach stable state
		String last_sets[] = new String[sets.length];
		while (!stable(last_sets)) {
			last_sets = sets.clone();
			// scan all rules
			for (int i = 0; i < grammar.size(); i++) {
				Production p = grammar.get(i);
				scan(p.from, p.to, 0);
			}
			// showFirstSet();
		}

	}

	public String getFirstSet(String s) {
		String output = "";
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			output = output + getFirstSet(c);
			int index = output.indexOf('l');
			if (index == -1) {
				return output;
			} else {
				// remove lemda
				output = output.substring(0, index)
						+ output.substring(index + 1);
			}
		}
		output += 'l';
		char[] array = output.toCharArray();
		Arrays.sort(array);
		output = String.valueOf(array);
		return output;
	}

	private void showGrammar() {
		for (int i = 0; i < grammar.size(); i++) {
			Production p = grammar.get(i);
			System.out.println(p.from + "->" + p.to);
		}
		System.out.println();
	}

	public void showFirstSet() {
		for (int i = 0; i < symbol.length; i++) {
			System.out.println(symbol[i] + ":{" + sets[i] + "}");
		}
		System.out.println();
	}

	private void scan(char from, String to, int i) {
		if (i < to.length()) {
			char cur_symbol = to.charAt(i);
			// System.out.println(cur_symbol);
			if (isTerminal(cur_symbol)) {
				union(from, cur_symbol);
			} else {// is non-terminal
				if (setHasLemda(cur_symbol)) { // lemda is in first(cur_symbol)
					unionWithoutLemda(from, cur_symbol);
					scan(from, to, i + 1);
				} else {
					unionString(from, getFirstSet(cur_symbol));
				}
			}
		} else {
			union(from, 'l');
		}

	}

	private void unionWithoutLemda(char from, char cur_symbol) {
		String set = getFirstSet(cur_symbol);
		int index = set.indexOf('l');
		set = set.substring(0, index) + set.substring(index + 1);
		unionString(from, set);
	}

	private void unionString(char from, String set) {
		String fromSet = getFirstSet(from);
		for (int i = 0; i < set.length(); i++) {
			char c = set.charAt(i);
			if (fromSet.indexOf(c) == -1) {
				fromSet = fromSet + c;
			}
		}
		char[] array = fromSet.toCharArray();
		Arrays.sort(array);
		fromSet = String.valueOf(array);
		setFirstSet(from, fromSet);
	}

	private boolean setHasLemda(char cur_symbol) {
		String set = getFirstSet(cur_symbol);
		int index = set.indexOf('l');
		return index != -1;
	}

	private boolean stable(String[] last_sets) {
		for (int i = 0; i < sets.length; i++) {
			if (!sets[i].equals(last_sets[i])) {
				return false;
			}
		}
		return true;
	}

	private void union(char c, char d) {
		String set = getFirstSet(c);
		// System.out.println(set);
		int index = set.indexOf(d);
		if (index == -1) {// add element d
			set = set + d;
			char[] array = set.toCharArray();
			Arrays.sort(array);
			set = String.valueOf(array);
			setFirstSet(c, set);
		}
	}

	private void setFirstSet(char c, String set) {
		int index = Arrays.binarySearch(symbol, c);
		sets[index] = set;
	}

	private boolean isTerminal(char c) {
		return !Character.isUpperCase(c);
	}

	public String getFirstSet(char c) {
		int index = Arrays.binarySearch(symbol, c);
		// System.out.println(c+" "+index);
		return sets[index];
	}

	private void getAllSymbol() {
		Stack<Character> symbols = new Stack<Character>();
		for (int i = 0; i < grammar.size(); i++) {
			Production p = grammar.get(i);
			if (symbols.search(p.from) == -1) {
				symbols.push(p.from);
			}
			for (int j = 0; j < p.to.length(); j++) {
				if (symbols.search(p.to.charAt(j)) == -1) {
					symbols.push(p.to.charAt(j));
				}
			}
		}
		symbol = new char[symbols.size()];
		for (int i = 0; i < symbol.length; i++) {
			symbol[i] = symbols.get(i);
		}
		Arrays.sort(symbol);
	}
}