Farmer John étudie la généalogie du troupeau : $M$ taureaux ($1 \le M \le 20$), $F$ vaches ($1 \le F \le 20$), mais ignore les descendances possibles.

Il connaît la séquence DNA unique $DNA_{i}$ de chacun. $DNA_{i}$ a longueur $25$, seulement A, $C$, G, T majuscules. Il cherche les enfants possibles de chaque couple taureau/vache.

Pour chaque couple affichez le nombre d'autres bovins pouvant être leurs enfants si :

1. le bovin n'est aucun des parents : une vache n'est pas sa mère ni un taureau son père ;

2. chaque position DNA correspond à au moins un parent à la même position.

Ainsi abc peut venir de (axx, xbc), pas de (aaa, bbb).

Considérez les séquences de $3$ taureaux et $2$ vaches :

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

Le taureau $2$ et la vache $1$ peuvent être parents de la vache $2$ :

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

Son premier A vient du taureau $2$, son deuxième T de la vache $1$, le reste de l'un ou l'autre.

Créez la matrice des nombres de descendants possibles pour chaque couple.

Entrée

• Ligne $1$ : entiers $M$ et $F$ séparés par un espace.

• Lignes $2..M+1$ : la ligne $i+1$ donne la séquence $DNA_{i}$ du taureau $i$.

• Lignes $M+2..M+F+1$ : la ligne $j+M+1$ donne la séquence $DNA_{j}$ de la vache $j$.

Sortie

• Lignes $1..M$ : ligne $i$, $F$ entiers séparés ; le $j$-ième compte les enfants possibles du taureau $i$ et de la vache $j$.

Exemples

Entrée 1

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

Sortie 1

2 1 0
0 0 2

Remarque

DNA de $2$ taureaux puis de $3$ vaches.

Considérez le taureau $1$ et la vache $1$ :

    b1: TGAAAAAAAAAAAAAAAAAAAAAAA
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA

La partie importante est {T|A} puis {G|T}.

Voici les tests de correspondance pour le taureau $0$ et la vache $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: taureau ; vache ; parent, ne peut être descendant ; descendant ! Correspond ; deuxième caractère A, doit être G ou T

Le premier élément vaut donc $2$, les autres sont similaires.

Auteur du problème : Jacob Steinhardt, 2010