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

此外，Laura 还有一组 $k$ 个颜色对 $S_1, \dots, S_k$，她非常不喜欢这些颜色对，因为它们在那种颜色和顺序下显得很丑，所以她在制作新项链时会尽量避免它们。

Laura 将以一种非常特殊的方式制作她的新项链。对于项链 $A$ 中的每一颗珍珠，她都会将其颜色与项链 $B$ 中每一颗珍珠的颜色进行组合。她的处理过程如下：

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

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

输入格式

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

接下来一行包含字符串 $A$，由恰好 $L_A$ 个来自集合 $[a-z]$ 的字符组成。

接下来一行包含字符串 $B$，由恰好 $L_B$ 个来自集合 $[a-z]$ 的字符组成。

接下来的 $k$ 行包含丑陋的组合，每行一个组合。这些组合被写成包含恰好 2 个来自集合 $[a-z]$ 的字符的字符串，并用单个空格分隔。

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

输出格式

输出应包含 $q$ 行，每行包含一个来自集合 $[a-z]$ 的字符，表示对 Laura 问题的回答，顺序与给定顺序相同。

数据范围

$1 \le L_A, L_B \le 200\,000$ $1 \le q \le 100\,000$ $0 \le k < 26^2$ 所有查询均指最终项链中的有效位置。

子任务

样例

样例输入 1

4 2 1 2
abcb
cc
c a
3
12

样例输出 1

c
b

说明 1

Laura 制作的项链为 ac ac bc bc cc cc bc bc（为了方便阅读插入了空格）。没有移除丑陋的组合。

样例输入 2

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

样例输出 2

c
c

说明 2

Laura 制作的项链为 ca cc ba ac ac（为了方便阅读插入了空格）。组合 bc、aa 和 aa 因为丑陋而被移除。