DNA 분석

DNA 연구를 하는 대학원생 민혁은 M (1 <= M <= 20)마리의 황소들과 F(1 <= F <= 20) 마리의 암소들의 유전자를 조사하고 있습니다. 그러나 그는 어떤 소들이 다른 소들의 가능한 후손인지 알 수 없습니다.

민혁은 모든 암소와 황소의 고유한 DNA 서열인 DNA_i를 알고 있습니다. DNA_i는 길이가 25인 문자열로 'A', 'C', 'G', 'T'의 대문자만 포함합니다. 그는 어떤 소가 어떤 황소와 암소의 쌍의 자식일 가능성이 있는지 알아내고자 합니다.

민혁을 도와주세요. 각 황소와 암소의 쌍에 대해, 민혁이 조사하고 있는 소들 중 얼마나 많은 소들이 그들의 자식이 될 수 있는지 출력하세요. 소는 다음의 조건을 만족하는 경우 주어진 황소와 암소의 자식이 될 수 있습니다.

1. 자기 자신의 DNA는 부모의 DNA가 될 수 없습니다. (즉, 암소는 그 자신의 어머니가 될 수 없고, 황소는 그 자신의 아버지가 될 수 없다).
2. DNA 서열의 각 위치의 문자는 두 부모 DNA 서열의 같은 위치에 있는 문자 중 하나와 일치해야 합니다.

따라서 예를 들어, 'abc'는 쌍 ('axx', 'xbc')에서 나올 수 있지만, 쌍 ('aaa', 'bbb')에서는 나올 수 없습니다.

다음 DNA 서열을 가진 세 마리의 황소(Bull)와 두 마리의 암소(Cow)를 생각해 봅시다:

       Bull 1: GTTTTTTTTTTTTTTTTTTTTTTTT
       Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
       Bull 3: GATTTTTTTTTTTTTTTTTTTTTTT
       Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT
       Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT

황소 2와 암소 1은 암소 2의 부모가 될 수 있습니다:

       Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
       Cow 1:  TTTTTTTTTTTTTTTTTTTTTTTTT
       Cow 2:  ATTTTTTTTTTTTTTTTTTTTTTTT

암소 2의 첫 번째 글자 'A'는 황소 2에서 왔을 수 있고, 암소 2의 두 번째 글자 'T'는 암소 1에서 왔을 수 있고, 나머지 글자들은 어느 부모에서든 올 수 있습니다.

당신의 목표는 각 황소와 암소의 쌍의 가능한 후손 수의 행렬을 만드는 것입니다.

• 1번째 줄 : 두 개의 공백으로 구분된 정수: M과 F
• 2번째 줄..M+1번째 줄 : i+1번째 줄은 황소 i의 DNA 서열을 제공합니다: DNA_i
• M+2번째 줄..M+F+1번째 줄 : j+M+1번째 줄은 암소 j의 DNA 서열을 제공합니다: DNA_j

• 1번째 줄..M번째 줄 : i번째 줄: F개의 공백으로 구분된 정수들. 
• j번째 정수는 i번째 황소와 j번째 암소의 자녀가 될 수 있는 소들의 수입니다.