Farmer John untersucht die Abstammung seiner Herde: $M$ Bullen ($1 \le M \le 20$), $F$ Kühe ($1 \le F \le 20$), kennt aber mögliche Nachkommen nicht.

Er kennt die eindeutige DNA-Sequenz $DNA_{i}$ jedes Tieres. $DNA_{i}$ hat Länge $25$, nur Großbuchstaben A, $C$, G, T. Gesucht sind mögliche Kinder jeder Bullen/Kuh-Paarung.

Gib für jedes Paar die Zahl anderer Tiere an, die Kinder sein können, wenn:

1. das Tier keiner der Eltern ist: Kuh nicht eigene Mutter, Bulle nicht eigener Vater;

2. jede DNA-Position mindestens einem Elternzeichen an derselben Position entspricht.

abc kann von (axx, xbc) stammen, nicht von (aaa, bbb).

Betrachte Sequenzen von $3$ Bullen und $2$ Kühen:

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

Bulle $2$ und Kuh $1$ können Eltern von Kuh $2$ sein:

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

Ihr erstes A kommt eventuell von Bulle $2$, zweites T von Kuh $1$, der Rest von einem der beiden.

Erstelle eine Matrix möglicher Kinderzahlen pro Paarung.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $M$ und $F$.

• Zeilen $2..M+1$: Zeile $i+1$ gibt Sequenz $DNA_{i}$ von Bulle $i$.

• Zeilen $M+2..M+F+1$: Zeile $j+M+1$ gibt Sequenz $DNA_{j}$ von Kuh $j$.

Ausgabe

• Zeilen $1..M$: Zeile $i$, $F$ getrennte ganze Zahlen; die $j$-te zählt mögliche Kinder von Bulle $i$ und Kuh $j$.

Beispiele

Eingabe 1

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

Ausgabe 1

2 1 0
0 0 2

Hinweis

DNA von $2$ Bullen, dann $3$ Kühen.

Betrachte Bulle $1$ und Kuh $1$:

    b1: TGAAAAAAAAAAAAAAAAAAAAAAA
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA

Der wichtige Teil ist {T|A} gefolgt von {G|T}.

Übereinstimmungstests für Bulle $0$ und Kuh $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: Bulle; Kuh; Elternteil, kein Nachkomme; Nachkomme! Passt; zweites Zeichen A, muss G oder T sein

Das erste Matrixelement ist $2$, andere entstehen ähnlich.

Aufgabenautor: Jacob Steinhardt, 2010