진주

Laura는 진주로 예쁜 목걸이를 만드는 것을 좋아한다. 그녀에게는 새 목걸이를 만들 때 본으로 삼고 싶은 두 목걸이 $A$와 $B$가 있다. 목걸이는 문자열로 나타내며, 각 문자는 목걸이에 있는 구슬 하나의 색을 나타낸다.

또한 Laura에게는 색과 순서가 보기 싫어서 정말 마음에 들어 하지 않는 $k$개의 색 쌍 $S_1, \cdots, S_k$이 있으며, 따라서 새 목걸이를 만들 때 이들을 피하려고 한다.

Laura는 특정한 방식으로 새 목걸이를 만든다. 목걸이 $A$의 처음부터 각 진주에 대해, 그 색을 목걸이 $B$에 있는 각 진주의 색과 조합한다.

목걸이 $A$의 각 진주 $A_i$에 대해, 목걸이 $B$의 각 진주 $B_j$를 살펴본다. 조합 $A_iB_j$이 보기 싫은 조합이 아니라면, 색이 $A_iB_j$인 진주들을 새 목걸이의 끝에 놓는다. 보기 싫은 조합이라면 아무것도 하지 않는다. Laura는 목걸이를 만드는 도중에만 보기 싫은 조합인지 확인하며, 새 목걸이에 진주들이 추가된 후에는 확인하지 않는다는 점에 유의한다.

Laura의 새 목걸이가 어떤 모습일지 알아내도록 도와주자. Laura에게는 $q$개의 질문이 있으며, 그중 $i$번째 질문 $t_i$은 새 목걸이의 $t_i$번째 진주의 색을 묻는다.

제약 조건

$1 \le L_A, L_B \le 2\cdot 10^5$

$1 \le q \le 10^5$

$0 \le k < 26^2$

모든 질의는 최종 목걸이에서 유효한 위치를 가리킨다.

채점

제출한 해답은 각각 일정한 점수가 배정된 테스트 그룹들의 집합으로 채점된다. 각 테스트 그룹은 테스트 케이스들의 집합을 포함한다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 배점 | 제약 조건

$1$ |$7$| $L_A = 1$

$2$ |$9$| $L_A, L_B \le 1000$

$3$ |$13$| $k = 0$

$4$ |$15$| $q \le 10$

$5$ |$56$| 추가 제약 조건이 없다.

첫 번째 줄에는 네 정수 $L_A, L_B, k$와 $q$가 주어진다. 이들은 각각 $A$의 길이, $B$의 길이, 보기 싫은 조합의 개수, 질문의 개수이다.

다음 줄에는 집합 $[a-z]$의 문자 정확히 $L_A$개로 이루어진 문자열 $A$이 주어진다.

다음 줄에는 집합 $[a-z]$의 문자 정확히 $L_B$개로 이루어진 문자열 $B$이 주어진다.

다음 $k$개 줄에는 한 줄에 하나씩 보기 싫은 조합이 주어진다. 이 조합들은 집합 $[a-z]$의 문자 정확히 2개가 공백 하나로 구분된 문자열로 작성된다.

다음 $q$개 줄에는 Laura가 최종 목걸이에서 구슬의 색을 알고 싶어 하는 위치들이 주어진다. 0은 목걸이의 첫 번째 위치이다.

$q$개 줄을 출력해야 하며, 각 줄에는 집합 $[a-z]$의 문자 하나를 출력한다. 이는 Laura의 질문에 대한 답을 질문이 주어진 순서대로 나타낸다.

Laura는 목걸이 ac ac bc bc cc cc bc bc을 만든다(읽기 쉽도록 공백을 삽입했다). 보기 싫은 항은 제거되지 않았다.

Laura는 목걸이 ca cc ba ac ac을 만든다(읽기 쉽도록 공백을 삽입했다). 항 bc, aa, aa은 보기 싫기 때문에 제거되었다.