Farmer John חוקר את היוחסין: $M$ שוורים ($1 \le M \le 20$), $F$ פרות ($1 \le F \le 20$), אך אינו יודע מי צאצא אפשרי של מי.

הוא יודע DNA ייחודי $DNA_{i}$ של כל חיה. $DNA_{i}$ באורך $25$, רק אותיות גדולות A, $C$, G, T. מחפש ילדים אפשריים לכל זוג שור/פרה.

לכל זוג הדפיסו כמה חיות אחרות יכולות להיות ילדיו אם:

1. החיה אינה אף הורה: פרה לא אמה של עצמה ושור לא אביו של עצמו;

2. כל מיקום 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

ה־A הראשון שלה משור $2$, ה־T השני מפרה $1$, השאר מכל הורה.

צרו מטריצה של מספר ילדים אפשריים לכל זוג.

קלט

• שורה $1$: השלמים $M$ ו־$F$ מופרדים ברווח.

• שורות $2..M+1$: שורה $i+1$ נותנת רצף $DNA_{i}$ של שור $i$.

• שורות $M+2..M+F+1$: שורה $j+M+1$ נותנת רצף $DNA_{j}$ של פרה $j$.

פלט

• שורות $1..M$: שורה $i$ עם $F$ שלמים; ה־$j$ סופר ילדים אפשריים של שור $i$ ופרה $j$.

דוגמאות

קלט 1

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

פלט 1

2 1 0
0 0 2

Note

DNA של $2$ שוורים ואחריהם $3$ פרות.

נבחן שור $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