// Arup Guha
// 3/13/2018
// Solution to 2018 UCF HS Contest Problem: Alphabet-Rearrange-Inator 3000

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

public class rearrange {

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int nC = Integer.parseInt(stdin.readLine().trim());

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			StringTokenizer tok = new StringTokenizer(stdin.readLine());
			int n = Integer.parseInt(tok.nextToken());
			int numQ = Integer.parseInt(tok.nextToken());

			// Set up our trie, and insert each word into it.
			node trie = new node();
			for (int i=0; i<n; i++) {
				String s = stdin.readLine().trim();
				trie.insert(s.toCharArray(), 0);
			}

			// Store output here.
			StringBuffer out = new StringBuffer();

			// Initial alphabet ordering.
			int[] perm = new int[26];
			for (int i=0; i<26; i++)
				perm[i] = i;

			// Process queries.
			for (int i=0; i<numQ; i++) {

				// Get the request.
				tok = new StringTokenizer(stdin.readLine());
				int q = Integer.parseInt(tok.nextToken());

				// Switch letters - sneaky, need to find where they are in perm.
				if (q == 1) {
					int loc1 = find(perm, tok.nextToken().charAt(0) - 'a');
					int loc2 = find(perm, tok.nextToken().charAt(0) - 'a');
					int tmp = perm[loc1];
					perm[loc1] = perm[loc2];
					perm[loc2] = tmp;
				}

				// Answer a query!
				else {
					int rank = Integer.parseInt(tok.nextToken())-1;
					out.append(trie.get(rank, perm)+"\n");
				}
			}

			// Output.
			System.out.println("Gift Exchange #"+loop+":");
			System.out.println(out);
		}
	}

	// Returns where in perm val is located.
	public static int find(int[] perm, int val) {
		for (int i=0; i<perm.length; i++)
			if (perm[i] == val)
				return i;
		return -1;
	}
}

class node {

	public int cnt;
	public String word;
	public node[] next;

	public node() {
		cnt = 0;
		word = null;
		next = new node[26];
		Arrays.fill(next, null);
	}

	public void insert(char[] s, int k) {

		// Got to bottom, count it.
		if (k == s.length) {
			cnt += 1;
			word = new String(s);
			return;
		}

		// Counting this word in this subtree.
		cnt += 1;

		int i = s[k] - 'a';

		// Make the next node to go to, if necessary.
		if (next[i] == null)
			next[i] = new node();

		// Recursively insert.
		next[i].insert(s, k+1);
	}

	// Get the ranked string according to permutation perm.
	public String get(int rank, int[] perm) {

		// Just find the one string in here.
		if (rank == 0) return getLeftMost(perm);

		int cur = 0, i = 0;

		// We need to count this word if it is one.
		if (word != null) cur = 1;

		// Skip everything we can.
		while (true) {
			int add = next[perm[i]] == null ? 0 : next[perm[i]].cnt;
			if (cur+add > rank) break;
			cur += add;
			i++;
		}

		// Recursively return the result.
		return next[perm[i]].get(rank-cur, perm);
	}

	public String getLeftMost(int[] perm) {

		// We found it.
		if (word != null) return word;

		// Find where to recurse.
		for (int i=0; i<26; i++)
			if (next[perm[i]] != null)
				return next[perm[i]].getLeftMost(perm);

		return "";
	}
}