题目背景

翻译自 NordicOI2021 的 A 题。

NordicOI2021 官网，需要使用 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$ 次询问的答案。

4 2 1 2
abcb
cc
c a
3
12

c
b

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

c
c

提示

对于 $100 \%$ 的数据，$1 \le la,lb \le 200000$，$1 \le q \le 100000$，$0 \le k \le 26^2$。

保证所有询问合法。