题目描述

Laura 喜欢用珍珠制作漂亮的项链。她有两条项链 $A$ 和 $B$，想用它们作为模板制作一条新的项链。

一条项链用一个字符串表示，每个字符表示一颗珍珠的颜色。

Laura 还有 $k$ 个她不喜欢的颜色有序对 $S_1,S_2,\ldots,S_k$。如果一个长度为 $2$ 的颜色组合在这些有序对中，她认为这个组合很丑，因此在制作新项链时会跳过它。

Laura 按如下方式制作新项链：

对于项链 $A$ 中的每一颗珍珠 $A_i$，按照从前到后的顺序，依次观察项链 $B$ 中的每一颗珍珠 $B_j$：

• 如果颜色组合 $A_iB_j$ 不是丑陋组合，则把颜色为 $A_i$ 和 $B_j$ 的两颗珍珠依次接到新项链末尾；
• 如果颜色组合 $A_iB_j$ 是丑陋组合，则什么也不做。

注意，Laura 只会在构造时判断组合是否丑陋；已经加入新项链中的相邻字符不会再被额外检查。

现在 Laura 有 $q$ 个询问。第 $i$ 个询问给出位置 $t_i$，要求回答新项链中第 $t_i$ 颗珍珠的颜色。位置从 $0$ 开始编号。

输入格式

第一行包含四个整数 $L_A,L_B,k,q$，分别表示 $A$ 的长度、$B$ 的长度、丑陋组合数量和询问数量。

第二行包含字符串 $A$，长度恰好为 $L_A$，只包含小写英文字母。

第三行包含字符串 $B$，长度恰好为 $L_B$，只包含小写英文字母。

接下来 $k$ 行，每行包含一个长度为 $2$ 的小写字母串，表示一个丑陋颜色组合。

接下来 $q$ 行，每行包含一个整数 $t_i$，表示一次询问的位置。

输出格式

输出 $q$ 行，每行一个小写英文字母，表示对应询问的答案。

数据范围

• $1 \le L_A,L_B \le 2\times 10^5$
• $1 \le q \le 10^5$
• $0 \le k < 26^2$
• 所有询问位置均保证在最终新项链的合法范围内。

子任务