뒤쥐 혈통학

몽고메리 모로 박사는 야생 북부 마다가스카르 얼룩 뒤쥐 무리를 여러 해 동안 관찰해 왔습니다. 그는 이 지역의 모든 뒤쥐를 꼼꼼히 기록하고, 각각의 두드러진 신체 특징을 적어 두었으며, 모든 개체에 이름을 붙였습니다.

각 특징(예: 갈색 털, 붉은 눈, 흰 발, 두드러진 앞니 등)에 대해 그는 그것이 우성인지 열성인지도 기록했습니다.

• 우성: 부모 중 한쪽이라도 그 특징을 가지고 있으면 자식도 그 특징을 가집니다. 즉, 부모 중 적어도 한쪽이 그 특징을 가진 경우에만 자식이 우성 특징을 가집니다.
• 열성: 부모 양쪽이 모두 그 특징을 가진 경우에만 자식이 그 특징을 가집니다. 즉, 부모 양쪽이 모두 그 특징을 가진 경우에만 자식이 열성 특징을 가집니다.

연구비 지원이 끊겨 박사가 몇 달간 자리를 비운 사이에 새로운 세대가 태어났습니다. 돌아온 그는 각 새끼에 대해 부모가 될 수 있는 어른 뒤쥐 쌍을 모두 알아내려 합니다.

한 새끼의 부모는 어른 암컷 한 마리(어미)와 어른 수컷 한 마리(아비)로 이루어집니다. 모든 특징에 대해 위 규칙을 두 어른에게 적용한 결과가 그 새끼의 값과 정확히 일치할 때, (어미, 아비) 쌍은 그 새끼의 부모가 될 수 있습니다.

첫 번째 줄에는 D와 R로 이루어진 길이 1 이상 80 이하의 문자열이 주어집니다. i번째 문자는 i번째 특징이 우성(D)인지 열성(R)인지를 나타냅니다.

그다음 줄들에는 어른 뒤쥐가 한 줄에 하나씩 주어집니다. 각 줄은 공백이 없는 1자 이상 32자 이하의 이름, 공백 한 칸, 성별을 나타내는 문자 M 또는 F, 다시 공백 한 칸, 그리고 특징별로 순서대로 나열된 0/1 문자열로 이루어집니다. 1은 그 특징을 가짐을, 0은 가지지 않음을 뜻합니다. 어른 목록은 ***만 있는 줄로 끝납니다.

그다음에는 새끼 뒤쥐를 설명하는 줄이 하나 이상 이어집니다. 각 새끼 줄은 같은 형식의 이름과 0/1 특징 문자열이 공백 한 칸으로 구분되어 주어지지만, 성별 항목은 없습니다(새끼의 성별은 사용하지 않습니다). 새끼 목록은 ***만 있는 줄로 끝납니다.

각 새끼에 대해 주어진 순서대로 한 줄씩 출력합니다. 새끼의 이름, 문자열 by, 그리고 그 새끼의 부모가 될 수 있는 어른 쌍의 목록을 이어서 출력합니다. 각 쌍은 어미의 이름, 하이픈, 아비의 이름 순으로 씁니다.

가능한 쌍이 둘 이상이면, 먼저 어미의 이름을 기준으로, 어미가 같은 쌍끼리는 아비의 이름을 기준으로 사전순으로 정렬하고, 이웃한 쌍은 문자열 or로 구분합니다. 부모가 될 수 있는 어른 쌍이 하나도 없으면, 새끼의 이름과 by만 출력하고 그 뒤에는 아무것도 쓰지 않습니다.