Farmer John은 계보를 연구합니다. 수소 $M$마리($1 \le M \le 20$), 암소 $F$마리($1 \le F \le 20$)지만 누가 누구의 후손일 수 있는지 모릅니다.
모든 소의 고유 DNA $DNA_{i}$를 압니다. $DNA_{i}$은 길이 $25$, 대문자 A, $C$, G, T만 있습니다. 각 수소·암소 쌍의 자식 가능성을 찾습니다.
각 쌍마다 자식일 수 있는 다른 소 수를 출력하며 조건은:
부모 어느 쪽도 아닌 것. 암소가 자신의 어미, 수소가 자신의 아비일 수 없습니다.
DNA 각 위치가 부모 같은 위치의 적어도 한 문자와 일치하는 것.
abc는 (axx, xbc)에서 가능하지만 (aaa, bbb)에서는 불가합니다.
수소 $3$마리와 암소 $2$마리의 서열을 봅니다.
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$, 두 번째 T는 암소 $1$, 나머지는 어느 부모에게서도 올 수 있습니다.
각 쌍의 가능한 자식 수 행렬을 만듭니다.
입력
$1$번 줄: 공백 구분 정수 $M$과 $F$.
$2..M+1$번 줄: $i+1$번 줄에 수소 $i$의 서열 $DNA_{i}$.
$M+2..M+F+1$번 줄: $j+M+1$번 줄에 암소 $j$의 서열 $DNA_{j}$.
출력
- $1..M$번 줄: $i$번 줄에 $F$개 공백 구분 정수. $j$번째는 수소 $i$와 암소 $j$의 가능한 자식 수.
예제
입력 1
2 3 TGAAAAAAAAAAAAAAAAAAAAAAA AGAAAAAAAAAAAAAAAAAAAAAAA ATAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAA TTAAAAAAAAAAAAAAAAAAAAAAA
출력 1
2 1 0 0 0 2
참고
수소 $2$마리 DNA 다음 암소 $3$마리 DNA입니다.
수소 $1$과 암소 $1$을 봅니다.
b1: TGAAAAAAAAAAAAAAAAAAAAAAA
c1: ATAAAAAAAAAAAAAAAAAAAAAAA중요 부분은 {T|A} 다음 {G|T}입니다.
수소 $0$과 암소 $0$의 일치 검사는 다음입니다.
b1: TGAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
b2: AGAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]
c1: ATAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
c2: AAAAAAAAAAAAAAAAAAAAAAAAA -- second character is 'A'; must be G or T
c3: TTAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]Bull / Cow; parent, can't be offspring; offspring! Matches; second character is A; must be G or T: 수소; 암소; 부모이므로 자식 불가; 자식! 일치; 두 번째는 A이고 G 또는 T여야 함
행렬 첫 원소는 $2$이며 나머지도 같습니다.
문제 출제자: Jacob Steinhardt, 2010