Farmer John has N spotted cows and N spotless cows. FD, like a geneticist, knows that spots on cows are caused by mutations at one position in the cow's genome.
For a lot of money, the FD issued the genomes of his cows. Each genome is a string of length M, built from four characters A, C, G, T. When he wrote them down, he got this table (for N=3):
Position: 1 2 3 4 5 6 7 ... M
Spotted Cow 1: A A T C C C A ... T
Spotted Cow 2: G A T T G C A ... A
Spotted Cow 3: G G T C G C A ... A
Stainless cow 1: A C T C C C A ... G
Stainless cow 2: A C T C G C A ... T
Stainless cow 3: A C T T C C A ... T
After carefully analyzing this table, he suggested that position 2 is a potential place in the genome that is responsible for spotting. Because in this position, cows without spots have the same symbol C, and spotted cows have symbols A or G. Moreover, G never appeared again in position 2. Position 1 cannot explain spotting, since A is in this position and spotted cows.
For given FD cow genomes, count the number of positions that could potentially explain spotting.
INPUT FORMAT:
The first line of input contains N and M, both positive integers up to 100. Each of the following N lines contains >M characters. They describe the genomes of spotted cows. The next N lines describe the genomes of spotless cows.
INPUT FORMAT:
Compute the number of genome positions (integer between 0…M) that could potentially explain spotting. Such positions can be predicted from given information.
| Input |
Output |
|
3 8
ATCCCAT
GATTGCAA
GGTCGCAA
ACTCCAG
ACTCGCAT
ACTTCCAT
|
1 |