Farmer John nghiên cứu phả hệ: $M$ bò đực ($1 \le M \le 20$), $F$ bò cái ($1 \le F \le 20$), nhưng không biết hậu duệ có thể của từng con.

Biết DNA duy nhất $DNA_{i}$ của mỗi con. $DNA_{i}$ dài $25$, chỉ chữ hoa A, $C$, G, T. Muốn tìm con có thể của mỗi cặp đực/cái.

Với mỗi cặp in số bò khác có thể là con nếu:

1. không là bố hoặc mẹ đó, bò cái không mẹ chính mình, bò đực không bố chính mình;

2. mỗi vị trí DNA khớp ít nhất một bố/mẹ tại cùng vị trí.

abc có thể từ (axx, xbc), không từ (aaa, bbb).

Xét trình tự $3$ bò đực và $2$ bò cái:

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

Bò đực $2$, bò cái $1$ có thể là bố mẹ bò cái $2$:

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

Chữ đầu A của cô từ đực $2$, chữ hai T từ cái $1$, còn lại từ bất kỳ bố mẹ nào.

Tạo ma trận số con có thể của mỗi cặp.

Dữ liệu vào

• Dòng $1$: số nguyên $M$ và $F$ cách nhau bởi dấu cách.

• Các dòng $2..M+1$: dòng $i+1$ cho trình tự $DNA_{i}$ của đực $i$.

• Các dòng $M+2..M+F+1$: dòng $j+M+1$ cho trình tự $DNA_{j}$ của cái $j$.

Dữ liệu ra

• Các dòng $1..M$: dòng $i$ có $F$ số nguyên; số thứ $j$ là số con có thể của đực $i$, cái $j$.

Ví dụ

Dữ liệu vào 1

2 3
TGAAAAAAAAAAAAAAAAAAAAAAA
AGAAAAAAAAAAAAAAAAAAAAAAA
ATAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAA
TTAAAAAAAAAAAAAAAAAAAAAAA

Dữ liệu ra 1

2 1 0
0 0 2

Ghi chú

DNA $2$ bò đực rồi $3$ bò cái.

Xét đực $1$, cái $1$:

    b1: TGAAAAAAAAAAAAAAAAAAAAAAA
    c1: ATAAAAAAAAAAAAAAAAAAAAAAA

Phần quan trọng là {T|A} rồi {G|T}.

Kiểm tra khớp cho đực $0$, cái $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: bò đực; bò cái; bố/mẹ, không thể là con; con! Khớp; ký tự hai A, phải là G hoặc T

Phần tử đầu là $2$, còn lại tương tự.

Tác giả bài toán: Jacob Steinhardt, 2010