String Puzzle

The magazine Amazing Coding runs a puzzle contest in every issue and gives away the latest digital gadgets as prizes. Its readers are programmers, so the magazine asks them to solve the puzzles by writing programs.

The puzzle in the latest issue is about deciding some of the letters of a string, called the secret string below, from a collection of hints. The figure shows one example of the hints.

The first hint is the length of the secret string. In the figure it is nine, and the nine boxes correspond to nine letters. Letter positions, that is box numbers, are counted from 1, from the left to the right.

Hints of the second kind give the letter of the secret string at a specific position. In the figure, the letters in boxes 3, 4, 7, and 9 are C, I, C, and P.

Hints of the third kind are about repeated substrings of the secret string. The bar immediately below the boxes is cut into sections, each covering a substring of the secret string. A section may be joined by a line running to the left with another section of the same length. The substrings covered by two joined sections are equal. One hint in the figure says that the letters in boxes 8 and 9 equal the letters in boxes 4 and 5, and from that you get the substring IP.

Not every pair of equal substrings of the secret string appears among the hints. Some pairs are left out.

Two joined sections may also overlap. In the figure, the two letter substring in boxes 2 and 3 is said to equal the one in boxes 1 and 2, and the two sections share box 2.

In this example every position of the secret string can be decided, and the string is CCCIPCCIP. In general the hints may not be enough to decide every letter.

The answer to the puzzle is the letters at the asked positions. Write a question mark ? when the letter at an asked position cannot be decided from the given hints.

The input consists of a single test case in the following format.

n a b q
x1 c1
.
.
.
xa ca
y1 h1
.
.
.
yb hb
z1
.
.
.
zq

The first line contains four integers $n$, $a$, $b$, and $q$. Here $n$ $(1 \le n \le 10^9)$ is the length of the secret string, $a$ $(0 \le a \le 1000)$ is the number of hints on letters at specified positions, $b$ $(0 \le b \le 1000)$ is the number of hints on repeated substrings, and $q$ $(1 \le q \le 1000)$ is the number of positions asked.

The $i$-th of the following $a$ lines contains an integer $x_i$ and an uppercase letter $c_i$, meaning that the letter at position $x_i$ of the secret string is $c_i$. These hints are ordered by position, that is $1 \le x_1 < \cdots < x_a \le n$.

The $i$-th of the following $b$ lines contains two integers $y_i$ and $h_i$. It is guaranteed that $2 \le y_1 < \cdots < y_b \le n$ and $0 \le h_i < y_i$. When $h_i$ is not 0, the substring of the secret string starting at position $y_i$ with length $y_{i+1} - y_i$ (with length $n + 1 - y_i$ when $i = b$) equals the substring of the same length starting at position $h_i$. A line with $h_i = 0$ tells nothing except that the substring specified in the line immediately above ends just before position $y_i$.

The $i$-th of the following $q$ lines contains an integer $z_i$ $(1 \le z_i \le n)$, the position of the letter to output.

At least one secret string matching all the given information exists. In other words, the hints have no contradiction.

Print a single line of $q$ characters. The $i$-th character of the output is the letter at position $z_i$ of the secret string when the hints decide it uniquely, and a question mark ? otherwise.