P11482 [NordicOI 2021] Pearls

翻译自 [NordicOI2021](https://github.com/nordicolympiad/nordic-olympiad-2021) 的 [A](https://github.com/nordicolympiad/nordic-olympiad-2021/blob/main/pdf/pearls.pdf) 题。 [NordicOI2021 官网](https://noi2021.nio.no/)，需要使用 Wayback machine 查看。

Laura 想要用两条项链 $A$ 和 $B$ 的颜色组合来制作一条新的项链，每个项链的颜色由字符串表示。而 Laura 希望避免 $k$ 个“丑陋”的颜色对。 Laura 以一种非常独特的方式制作她的新项链。对于项链 $A$ 中的每一颗珍珠，她都将其与项链 $B$ 中每一颗珍珠进行组合。具体步骤如下： 对于项链 $A$ 中的每一颗珍珠 $A_i$，她会查看项链 $B$ 中的每一颗珍珠 $B_j$。如果组合 $A_i,B_j$ 不是丑陋的组合，她就在新项链的末尾放置颜色为 $A_i$ 和 $B_j$ 的珍珠。 帮助 Laura 确定她的项链的样子。有 $q$ 次询问，对于第 $i$ 次询问，有一个整数 $t_i$ 表示询问新项链中第 $t_i$ 个珠子的颜色。

第一行有四个整数 $la,lb,k,q$。其中 $la$ 表示 $A$ 项链的长度，$lb$ 表示 $B$ 项链的长度，$k$ 表示丑陋对的个数，$q$ 表示询问的次数。 第二行有一个字符串 $a$，表示 $A$ 项链的颜色，只存在小写字母。 第三行有一个字符串 $b$，表示 $B$ 项链的颜色，只存在小写字母。 往后 $k$ 行每行两个小写字母，用空格隔开。表示每个丑陋对。 再往后 $q$ 行表示询问。注意，项链的下标从 $0$ 开始。

你需要输出 $q$ 行，对于第 $i$ 行，你需要输出一个小写字母代表第 $i$ 次询问的答案。

| Subtask | 分数 | 约束 | | :----------: | :----------: | :----------: | | Subtask $0$ | $7$ | $la=1$ | | Subtask $1$ | $9$ | $la,lb \le 1000$ | | Subtask $2$ | $13$ | $k=0$ | | Subtask $3$ | $15$ | $q \le 10$ | | Subtask $4$ | $56$ | 没有特殊限制 | 对于 $100 \%$ 的数据，$1 \le la,lb \le 200000$，$1 \le q \le 100000$，$0 \le k \le 26^2$。 保证所有询问合法。