DNA Sequencing

Farmer John is studying the genealogy of his herd. He has $M$ bulls ($1 \le M \le 20$) and $F$ cows ($1 \le F \le 20$), but he does not know which bovines could be descendants of which others.

Farmer John does know the DNA sequence of every cow and bull on his farm. Each DNA sequence has length 25 and contains only the upper-case letters A, C, G, and T. He wants to determine which bovines could possibly be children of which cow-and-bull pairs.

A bovine can be a child of a given bull and cow when:

1. it is neither of the two parents (a bovine cannot be its own mother or father);
2. at every position, its DNA character equals the character at the same position in at least one of the two parents.

For example, abc could be a child of the pair (axx, xbc), but not of the pair (aaa, bbb).

As a conceptual illustration, consider three bulls and two cows:

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

Bull 2 and Cow 1 could be the parents of Cow 2: Cow 2's first letter A can come from Bull 2, its second letter T can come from Cow 1, and every remaining letter can come from either parent.

For every pairing of a bull and a cow, report how many of Farmer John's other bovines could be their child.

• Line 1: two space-separated integers $M$ and $F$.
• Lines 2 to $M+1$: line $i+1$ contains the DNA sequence of bull $i$.
• Lines $M+2$ to $M+F+1$: line $j+M+1$ contains the DNA sequence of cow $j$.

Print $M$ lines. Line $i$ contains $F$ space-separated integers; the $j$-th integer is the number of bovines that could be children of bull $i$ and cow $j$.

Take bull 1 (TGA...) and cow 1 (ATA...) from the sample. The important part of their combined DNA is {T|A} in the first position, {G|T} in the second, and A everywhere else. Checking every other bovine:

TGA... -- a parent, cannot be a child
AGA... -- child! matches [TA][GT]
ATA... -- a parent, cannot be a child
AAA... -- second character 'A' must be 'G' or 'T', so not a child
TTA... -- child! matches [TA][GT]

Two bovines qualify, so the top-left entry of the answer matrix is 2. Every other entry is computed the same way.