Farmer John bada rodowód: $M$ byków ($1 \le M \le 20$), $F$ krów ($1 \le F \le 20$), lecz nie zna możliwych potomków.

Zna unikalną sekwencję DNA $DNA_{i}$ każdego. $DNA_{i}$ ma długość $25$, tylko wielkie A, $C$, G, T. Szuka możliwych dzieci każdej pary byk/krowa.

Dla każdej pary wypisz liczbę innych zwierząt mogących być dziećmi, jeśli:

1. nie są żadnym rodzicem: krowa nie własną matką, byk nie własnym ojcem;

2. każda pozycja DNA pasuje do przynajmniej jednego rodzica w tej pozycji.

abc może pochodzić od (axx, xbc), nie od (aaa, bbb).

Rozważ sekwencje $3$ byków i $2$ krów:

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

Byk $2$ i krowa $1$ mogą być rodzicami krowy $2$:

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

Jej pierwsze A może być od byka $2$, drugie T od krowy $1$, reszta od dowolnego rodzica.

Utwórz macierz liczb możliwych dzieci każdej pary.

Wejście

• Wiersz $1$: całkowite $M$ i $F$ oddzielone spacją.

• Wiersze $2..M+1$: wiersz $i+1$ podaje sekwencję $DNA_{i}$ byka $i$.

• Wiersze $M+2..M+F+1$: wiersz $j+M+1$ podaje sekwencję $DNA_{j}$ krowy $j$.

Wyjście

• Wiersze $1..M$: wiersz $i$ ma $F$ całkowitych; $j$-ta liczy możliwe dzieci byka $i$ i krowy $j$.

Przykład

Wejście 1

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

Wyjście 1

2 1 0
0 0 2

Uwagi

DNA $2$ byków, potem $3$ krów.

Rozważ byka $1$ i krowę $1$:

    b1: TGAAAAAAAAAAAAAAAAAAAAAAA
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA

Ważna część to {T|A}, potem {G|T}.

Testy dopasowania dla byka $0$ i krowy $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: byk; krowa; rodzic, nie może być potomkiem; potomek! Pasuje; drugi znak A, musi być G lub T

Pierwszy element jest $2$, pozostałe analogicznie.

Autor zadania: Jacob Steinhardt, 2010