DNA 시퀀싱

Farmer John이 자기 소 떼의 혈통을 연구하고 있다. 농장에는 수소 $M$마리($1 \le M \le 20$)와 암소 $F$마리($1 \le F \le 20$)가 있지만, 어떤 소가 어떤 소의 자손이 될 수 있는지는 알지 못한다.

다만 농장에 있는 모든 소의 DNA 서열은 알고 있다. 각 DNA 서열의 길이는 25이고, 대문자 A, C, G, T로만 이루어져 있다. Farmer John은 각 (수소, 암소) 쌍에 대해 어떤 소들이 그 둘의 자식이 될 수 있는지 알아내려고 한다.

어떤 소가 특정 수소와 암소의 자식이 되려면 다음 두 조건을 모두 만족해야 한다.

1. 그 소가 두 부모 중 어느 쪽도 아니다(어떤 소도 자기 자신의 부모가 될 수 없다).
2. 모든 위치에서 그 소의 DNA 문자가 같은 위치에 있는 두 부모의 문자 중 적어도 하나와 일치한다.

예를 들어 abc는 쌍 (axx, xbc)의 자식이 될 수 있지만, 쌍 (aaa, bbb)의 자식은 될 수 없다.

개념을 설명하기 위한 예로 수소 3마리와 암소 2마리를 생각해 보자.

수소 1: GTTTTTTTTTTTTTTTTTTTTTTTT
수소 2: AATTTTTTTTTTTTTTTTTTTTTTT
수소 3: GATTTTTTTTTTTTTTTTTTTTTTT
암소 1: TTTTTTTTTTTTTTTTTTTTTTTTT
암소 2: ATTTTTTTTTTTTTTTTTTTTTTTT

수소 2와 암소 1은 암소 2의 부모가 될 수 있다. 암소 2의 첫 글자 A는 수소 2에서, 둘째 글자 T는 암소 1에서 올 수 있고, 나머지 글자는 두 부모 어느 쪽에서든 올 수 있기 때문이다.

각 (수소, 암소) 쌍에 대해, Farmer John의 다른 소들 중 그 둘의 자식이 될 수 있는 소가 몇 마리인지 구하라.

• 첫째 줄: 공백으로 구분된 두 정수 $M$과 $F$.
• 둘째 줄부터 $M+1$번째 줄까지: $i+1$번째 줄에 수소 $i$의 DNA 서열이 주어진다.
• $M+2$번째 줄부터 $M+F+1$번째 줄까지: $j+M+1$번째 줄에 암소 $j$의 DNA 서열이 주어진다.

$M$개의 줄을 출력한다. $i$번째 줄에는 공백으로 구분된 $F$개의 정수를 출력하며, $j$번째 정수는 수소 $i$와 암소 $j$의 자식이 될 수 있는 소의 수이다.

예제의 수소 1(TGA...)과 암소 1(ATA...)을 살펴보자. 두 부모 DNA의 핵심은 첫 위치가 {T|A}, 둘째 위치가 {G|T}이고 나머지는 모두 A라는 점이다. 다른 모든 소를 확인해 보면 다음과 같다.

TGA... -- 부모이므로 자식이 될 수 없음
AGA... -- 자식! [TA][GT]에 부합
ATA... -- 부모이므로 자식이 될 수 없음
AAA... -- 둘째 글자 'A'는 'G'나 'T'여야 하므로 자식 아님
TTA... -- 자식! [TA][GT]에 부합

두 마리가 조건을 만족하므로 답 행렬의 첫 원소는 2이다. 나머지 원소도 같은 방식으로 계산한다.