문자열 퍼즐

잡지 Amazing Coding은 매 호마다 퍼즐 대회를 열고 최신 디지털 기기를 상품으로 준다. 독자가 프로그래머이므로 잡지는 퍼즐을 프로그램으로 풀어 보라고 권한다.

이번 호의 퍼즐은 여러 힌트를 보고 비밀 문자열의 일부 글자를 알아내는 문제다. 아래 그림은 힌트의 예다.

첫 번째 힌트는 비밀 문자열의 길이다. 위 그림에서는 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
x1 c1
.
.
.
xa ca
y1 h1
.
.
.
yb hb
z1
.
.
.
zq

첫 줄에 정수 네 개 $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 < \cdots < x_a \le n$이다.

이어지는 $b$개 줄 중 $i$번째 줄에는 정수 $y_i$와 $h_i$가 주어진다. $2 \le y_1 < \cdots < 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$개 줄 중 $i$번째 줄에는 출력할 글자의 위치 $z_i$ $(1 \le z_i \le n)$가 주어진다.

주어진 정보를 모두 만족하는 비밀 문자열이 적어도 하나 존재함이 보장된다. 즉 힌트끼리 모순되지 않는다.

문자 $q$개로 이루어진 한 줄을 출력한다. 출력의 $i$번째 문자는 힌트로 비밀 문자열의 $z_i$번 위치의 글자가 유일하게 정해지면 그 글자이고, 정해지지 않으면 물음표 ?이다.