时间限制： 1.0 秒

空间限制： 512 MB

题目描述

本题涉及字符包括大小写字母（A-Z 和 a-z）、数字（0-9）和空格共 $63$ 种。在这个字符集合上，小 P 定义了一个字符替换函数 $f(ch)$，表示将字符 $ch$ 替换为 $f(ch)$。 例如 $f(a) = b$ 表示将 a 替换为 b，$f(b) = 0$ 表示将 b 替换为 0。 进而可以将其扩展为字符串变换函数 $F(s)$，表示对字符串 s 进行变换，将 s 中每个字符 $ch$ 都替换为 $f(ch)$。

字符替换函数 $f$ 可表示为 $n$ 个字符对 $(ch_1, ch_2)$，即 $f(ch_1) = ch_2$。

• $n$ 个字符对中，$ch_1$ 两两不同，即不会出现同时定义了 $f(a) = b$ 和 $f(a) = 0$ 的情况；
• 未定义的 $f(ch)$，可视为 $f(ch) = ch$，即字符 $ch$ 保持不变；
• 函数 $f$ 为单射，即当 $ch1 \neq ch2$ 时有 $f(ch1) \neq f(ch2)$，例如不会同时有 $f(b) = 0$ 和 $f(0) = 0$（b 和 0 都被替换为 0）。

现给定初始字符串 s，试处理 $m$ 个查询：每个查询包含一个正整数 $k$，询问对初始字符串 s 变换 $k$ 次后的结果 $F^{k}(s)$。

输入格式

从标准输入读入数据。

输入共 $n + 4$ 行。

输入的第一行包含一个字符串，形如 #s#，即用两个井号字符 # 将初始字符串 s 囊括其中。

输入的第二行包含一个正整数 $n$，表示组成函数 $f$ 的字符对数；接下来 $n$ 行每行输入一个形如 #xy# 的字符串，表示 $f(x) = y$。

输入的第 $n+3$ 行包含一个正整数 $m$，表示查询的个数；下一行包含空格分隔的 $m$ 个正整数 $k_1, k_2, \cdots, k_m$，表示 $m$ 个查询。

输出格式

输出到标准输出。

输出共 $m$ 行，依次输出 $m$ 个查询的结果；输出时每行同样是一个形如 #s# 的字符串，即用两个井号把变换后的字符串 s 括起。

#Hello World#
6
#HH#
#e #
# r#
#re#
#oa#
#ao#
3
1 2 3

#H llarWaeld#
#HrlloeWo ld#
#Hella Warld#

子任务

前 $60\%$ 的测试数据保证初始字符串 s 仅包含小写字母，且输入的 $n$ 个字符对也皆为小写字母（即保证小写字母仅会被替换为小写字母）；

前 $80\%$ 的测试数据保证查询数量 $m \le 10$、变换次数 $k \le 100$；

全部测试数据保证 $0 < n \le 63$、$0 < m \le 10^{3}$、$0 < k \le 10^{9}$ 且初始字符串 s 包含不超过 100 个字符。

提示

由于读入的字符串中包含空格字符，推荐使用按行读取的方式，避免读入时跳过空格（如 cin 直接读入字符串）。

C 语言：可以使用 fgets() 函数读入整行，fgets(s, count, stdin) 会从标准连续输入读入至多 count - 1 个字符，并存入字符数组 s，直到遇到换行符或文件末尾为止。在前一种情况下，s 结尾处会存有读入的换行符。也可使用 getchar() 函数逐个字符读入，如 char ch = getchar();，这种方法需手动判断是否到达行末，即返回值是否为 \n。

C++：可以使用 std::getline() 函数读入整行：std::getline(std::cin, s) 会从标准输入读入字符，并存入字符串 std::string s 中，直到换行符或文件末尾为止。在前一种情况下，换行符会从标准输入中读出，但不会存入字符串 s 中。

Python：使用 input() 函数即可读入整行。