题目描述
题目译自 NordicOI 2021 T1 「Pearls」

Laura 喜欢用珍珠制作漂亮的项链。她有两条项链 A 和 B，她想用它们作为模板来制作一条新项链。项链用一个字符串表示，每个字符代表项链上的一个珠子的颜色。

此外，Laura 有 $k$ 对颜色组合 $S_1, \cdots, S_k$，她非常不喜欢这些组合，因为它们的颜色和顺序很丑，所以她在制作新项链时会尽量避免这些组合。

Laura 将以一种特定的方式制作她的新项链。对于项链 A 中的每一个珠子，她会将其颜色与项链 B 中每一个珠子的颜色组合。

对于项链 A 中的每一个珠子 $A_i$，她会查看项链 B 中的每一个珠子 $B_j$。如果组合 $A_iB_j$ 不是一个丑陋的组合，她会将颜色为 $A_iB_j$ 的珠子放在新项链的末尾。如果是丑陋的组合，她什么也不做。注意，Laura 只在构建项链时检查丑陋的组合，而不是在它们被添加到新项链之后。

帮助 Laura 确定她的新项链会是什么样子。Laura 有 $q$ 个问题，第 $i$ 个问题 $t_i$ 询问新项链上第 $t_i$ 个珠子的颜色。

---

输入格式

第一行包含四个整数 $L_A$, $L_B$, $k$ 和 $q$。它们分别是 A 的长度，B 的长度，丑陋组合的数量和问题的数量。

接下来的一行包含字符串 A，由恰好 $L_A$ 个小写字母组成。

接下来的一行包含字符串 B，由恰好 $L_B$ 个小写字母组成。

接下来的 $k$ 行包含丑陋组合，每行一个组合。这些组合写成由恰好两个小写字母组成的字符串，用一个空格分隔。

接下来的 $q$ 行是 Laura 想知道新项链上珠子颜色的位置。项链的第一个位置是 0。

---

输出格式

输出应包含 $q$ 行，每行包含一个字符，表示按给定顺序回答 Laura 的问题。

---

样例 1

输入：

4 2 1 2
abcb
cc
c a
3
12

输出：

c
b

解释：Laura 创建了项链 ac ac bc bc cc cc bc bc（为了便于阅读插入了空格）。没有丑陋的组合被移除。

---

样例 2

输入：

4 2 2 2
cbaa
ac
b c
a a
7
7

输出：

c
c

解释：Laura 创建了项链 ca cc ba ac ac（为了便于阅读插入了空格）。组合 bc、aa 和 aa 被移除，因为它们是丑陋的。

---

数据范围与提示

对于所有输入数据，满足：

• $1 \le L_A, L_B \le 2 \cdot 10^5$
• $1 \le q \le 10^5$
• $0 \le k < 26^2$
• 所有查询都指向新项链中的合法位置

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	7	$L_A = 1$
2	9	$L_A, L_B \le 1000$
3	13	$k = 0$
4	15	$q \le 10$
5	56	无附加限制