마스터마인드 암호 추리

마스터마인드(MasterMind)는 루마니아의 통신 기술자 모르드카이 메이로비츠(Mordechai Meirovitz)가 1971년에 만든 논리 게임입니다. 1974년에는 권위 있는 "올해의 게임" 상을 받았고, 40개국 이상에서 판매될 만큼 상업적으로도 큰 성공을 거두었습니다.

마스터마인드에서 여러분의 목표는 상대가 정한 비밀 암호를 알아내는 것입니다. 암호는 주어진 문자 집합(알파벳)에서 뽑은 문자들의 나열입니다. 암호를 알아내기 위해 여러분은 추측(guess)을 제출합니다. 추측이란 암호의 후보로, 암호와 길이가 같고 같은 알파벳의 문자로 이루어진 문자열입니다.

추측을 제출할 때마다, 그 추측이 얼마나 좋았는지를 나타내는 두 정수 $(E, G)$로 이루어진 응답을 받습니다.

• 추측의 어떤 문자가 암호의 같은 위치에 존재하면 "훌륭함(excellent)"으로 세어 $E$에 포함합니다.
• 그렇지 않고 어떤 문자가 추측과 암호 양쪽에 모두 있지만 다른 위치에 있으면 "좋음(good)"으로 세어 $G$에 포함합니다.
• 추측의 한 문자는 두 번 세지 않습니다(훌륭함으로 셌다면 좋음으로는 세지 않습니다).

아래 표는 몇 가지 예시를 보여 줍니다.

여러 번의 추측과 그 응답을 종합하면 암호를 추론할 수 있습니다. 추측들과 그에 대한 응답이 주어질 때, 암호에 대해 확정할 수 있는 정보를 모두 구하세요. 유일하게 결정되는 위치에는 그 문자를, 결정할 수 없는 위치에는 '?'를 출력합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $L$, $K$가 주어집니다. $N$은 추측의 수($0 \le N \le 1000$), $L$은 암호의 길이($1 \le L \le 4$), $K$는 사용하는 알파벳의 크기($1 \le K \le 18$)입니다. 다음 줄에는 알파벳을 이루는 $K$개의 문자가 구분 기호 없이 주어지며, 각 문자는 숫자('0'–'9') 또는 대문자('A'–'Z')입니다. 이어지는 $N$개의 줄에는 각각 하나의 추측(알파벳 문자로 이루어진 길이 $L$의 문자열)과 그 추측에 대한 응답인 두 정수 $E$, $G$가 주어집니다.

입력의 끝은 $N = L = K = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

입력은 표준 입력으로 읽어야 합니다.

각 테스트 케이스마다, 추측과 응답으로부터 확정할 수 있는 정보를 한 줄에 출력합니다. 모든 추측과 응답에 부합하는 모든 가능한 암호에서 어떤 위치의 문자가 항상 같다면 그 문자를, 그렇지 않으면 그 위치에 '?'를 출력합니다. 특히 추측과 응답이 서로 모순되어 부합하는 암호가 하나도 없으면 모든 위치에 '?'를 출력합니다.

출력은 표준 출력으로 써야 합니다.