바이킹 해커

바이킹이 뛰어난 전사였다는 사실은 대부분 알고 있겠지만, 그들에게 뛰어난 프로그래머도 있었다는 사실은 잘 알려져 있지 않다. 룬석을 프로그래밍하려면 많은 시간이 필요했고 실수할 여지가 거의 없었다. 하지만 안타깝게도 이로 인해 룬석은 자유롭게 활개 치던 바이킹 해커에게 특히 취약해졌다.

여러분은 이 시대의 룬석을 문자와 그 이진 표현이 수록된 참고서를 사용하여 번역하는 임무를 맡았다 (바이킹에게는 고급 언어가 없었으므로 일과 영을 사용해 직접 코딩했다). 그러나 대부분의 룬석은 결국 해킹당했으므로 코드의 일부가 잘못되었을 가능성이 있다.

점수 산정

여러분의 풀이는 여러 테스트 케이스 그룹에 대해 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$30$| $T = 1$

$2$ |$70$| 추가 제한이 없다.

첫째 줄에 알파벳에 포함된 문자의 수를 나타내는 수 $T$ ($1 \le T \le 16$)가 주어진다.

그다음 $T$개의 줄에 문자 하나(대문자와 소문자 a-z 및 숫자가 나올 수 있다)와 그 문자의 이진 표현 (항상 길이가 4인 일과 영의 수열)이 주어진다. 마지막으로 번역해야 할 룬석인, 일과 영 $N$ ($1 \leq N \leq 4\,000)$개로 이루어진 길이 $N$의 문자열이 주어진다. $N$은 $4$로 나누어떨어지며, 입력에는 이진 표현이 같은 서로 다른 두 문자가 없음이 보장된다.

룬석의 번역인 $N$개의 문자로 이루어진 한 줄을 출력한다. 올바르게 번역할 수 없었던 문자는 대신 "?"을 출력한다.

0100은 a로 번역해야 하고, 1000은 b로 번역해야 한다는 것을 알 수 있다. 번역해야 할 문자열은 0100100000101000이며, 이를 문자 0100, 1000, 0010, 1000로 나눌 수 있다. 세 번째 문자만 번역할 수 없으므로 출력은 ab?b이 된다.