题目描述

题目译自 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 的问题。

4 2 1 2
abcb
cc
c a
3
12

c
b

Laura 创建了项链 $\texttt{ac ac bc bc cc cc bc bc}$（为了便于阅读插入了空格）。 没有丑陋的组合被移除。

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

c
c

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

数据范围与提示

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

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

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