《Amazing Coding Magazine》因其举办的益智解谜竞赛而受到年轻程序员的欢迎，竞赛奖品是诱人的数码产品。该杂志自然也鼓励读者通过编写程序来解决这些谜题。让我们试一试！

最新一期的谜题是根据各种提示确定一个字符串（下文称为“秘密字符串”）中的某些字母。下图展示了所给提示的一个示例。

第一个提示是秘密字符串的长度。在上图的示例中，长度为 9，9 个方框对应 9 个字母。字母位置（方框）从左到右编号，起始编号为 1。

下一类提示简单地给出了秘密字符串在某些特定位置的字母。在示例中，提示给出了第 3、4、7 和 9 个方框中的字母分别为 C、I、C 和 P。

最后一类提示关于秘密字符串中的重复子串。图中方框下方的长条被划分为若干部分，对应于秘密字符串的子串。其中一些部分可以通过向左延伸的连线连接到另一个同样表示子串范围的长条。每一对连接的区域表示这两个范围内的子串是相同的。示例中的这类提示之一告诉我们，第 8 和第 9 个方框中的字母与第 4 和第 5 个方框中的字母分别相同。由此，你可以轻易推断出该子串为 IP。

注意，秘密字符串中并非所有相同的子串对都会在提示中给出；有些相同的子串对可能未被提及。

还要注意，一对中的两个范围可能会相互重叠。在示例中，第 2 和第 3 个方框组成的双字母子串被告知与第 1 和第 2 个方框组成的子串相同，这两个范围共享第 2 个方框。

在这个示例中，你可以确定秘密字符串所有位置的字母，即“CCCIPCCIP”。通常情况下，提示可能不足以确定秘密字符串中的所有字母。

谜题的答案应为秘密字符串中指定位置的字母。当指定位置的字母无法根据所给提示确定时，应回答符号 ?。

输入格式

输入包含单个测试用例，格式如下：

$n \ a \ b \ q$ $x_1 \ c_1$ $\vdots$ $x_a \ c_a$ $y_1 \ h_1$ $\vdots$ $y_b \ h_b$ $z_1$ $\vdots$ $z_q$

第一行包含四个整数 $n, a, b, q$。$n$ ($1 \le n \le 10^9$) 是秘密字符串的长度，$a$ ($0 \le a \le 1000$) 是关于指定位置字母的提示数量，$b$ ($0 \le b \le 1000$) 是关于重复子串的提示数量，$q$ ($1 \le q \le 1000$) 是询问的位置数量。

接下来的 $a$ 行中，第 $i$ 行包含一个整数 $x_i$ 和一个大写字母 $c_i$，表示秘密字符串在位置 $x_i$ 的字母为 $c_i$。这些提示按位置排序，即 $1 \le x_1 < \dots < x_a \le n$。

接下来的 $b$ 行中，第 $i$ 行包含两个整数 $y_i$ 和 $h_i$。保证满足 $2 \le y_1 < \dots < y_b \le n$ 且 $0 \le h_i < y_i$。当 $h_i$ 不为 0 时，从位置 $y_i$ 开始且长度为 $y_{i+1}-y_i$（当 $i=b$ 时为 $n+1-y_i$）的子串，与从位置 $h_i$ 开始且长度相同的子串相同。$h_i=0$ 的行不提供任何提示，仅表示该行中的 $y_i$ 指示了上一行所指定子串的结束位置。

接下来的 $q$ 行，每行包含一个整数 $z_i$ ($1 \le z_i \le n$)，指定要输出的秘密字符串中字母的位置。

保证至少存在一个符合所有给定信息的秘密字符串。换句话说，给定的提示没有矛盾。

输出格式

输出应为一行，仅包含 $q$ 个字符。输出中第 $i$ 个字符应为秘密字符串在位置 $z_i$ 的字母（如果能根据提示唯一确定），否则输出 ?。

样例

样例输入 1

9 4 5 4
3 C
4 I
7 C
9 P
2 1
4 0
6 2
7 0
8 4
8
1
9
6

样例输出 1

ICPC

样例输入 2

1000000000 1 1 2
20171217 A
3 1
42
987654321

样例输出 2

?A