Farmer John sở hữu \(N\) con bò có đốm và \(N\) con bò không có đốm. Vừa hoàn thành một khóa học về di truyền học ở bò, ông tin rằng các đốm trên bò của mình là do những đột biến tại một vị trí duy nhất trong hệ gen của bò.

Farmer John phải bỏ ra một khoản chi phí rất lớn để giải trình tự hệ gen của đàn bò. Mỗi hệ gen là một chuỗi độ dài \(M\) được tạo bởi bốn ký tự A, C, G và T. Khi căn chỉnh hệ gen của các con bò, ông thu được một bảng như sau, minh họa với \(N=3\):

Vị trí:         1 2 3 4 5 6 7 ... M

Bò đốm 1:       A A T C C C A ... T
Bò đốm 2:       G A T T G C A ... A
Bò đốm 3:       G G T C G C A ... A

Bò không đốm 1: A C T C C C A ... G
Bò không đốm 2: A C T C G C A ... T
Bò không đốm 3: A C T T C C A ... T

Quan sát kỹ bảng này, ông phỏng đoán rằng vị trí \(2\) có thể là một vị trí trong hệ gen giải thích được đặc điểm có đốm. Nghĩa là chỉ cần nhìn vào ký tự tại vị trí này, Farmer John có thể dự đoán con bò nào có đốm và con bò nào không có đốm (ở đây, A hoặc G biểu thị bò đốm còn C biểu thị bò không đốm; T không liên quan vì không xuất hiện ở vị trí \(2\) trong bất kỳ con bò nào của Farmer John). Riêng vị trí \(1\) không đủ để giải thích đặc điểm có đốm, vì ký tự A tại vị trí này có thể thuộc về một con bò đốm hoặc một con bò không đốm.

Cho hệ gen của đàn bò Farmer John, hãy đếm số vị trí mà mỗi vị trí tự nó có thể giải thích được đặc điểm có đốm.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\), cả hai đều là số nguyên dương không lớn hơn \(100\). \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(M\) ký tự, mô tả hệ gen của các con bò đốm. \(N\) dòng cuối mô tả hệ gen của các con bò không đốm.

Dữ liệu ra

In số vị trí trong hệ gen có khả năng giải thích đặc điểm có đốm (một số nguyên trong khoảng \(0 \ldots M\)). Một vị trí có khả năng giải thích đặc điểm có đốm nếu chỉ bằng cách quan sát vị trí đó trong hệ gen, ta có thể dự đoán hoàn toàn chính xác đặc điểm có đốm trong quần thể bò của Farmer John.

Ví dụ

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

1

Nguồn

USACO 2017 US Open Contest, Bronze — Bovine Genomics. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=736