Bovine Genomics (Bronze)#10522
Farmer John owns spotty cows and plain cows. Having just completed a course in bovine genetics, he is convinced that the spots on his cows are caused by mutations at a single location in the bovine genome.
At great expense, Farmer John sequences the genomes of all his cows. Each genome is a string of length consisting of the four characters A, C, G, and . When he lines up the genomes of his cows, he obtains a table like the following, shown here for n = 3:
Positions: 1 2 3 4 5 6 7 ... m
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A C T C G C A ... T
Plain Cow 3: A C T T C C A ... TLooking carefully at this table, he realizes that position is a candidate location that could explain the spottiness. That is, by looking only at the character at this position, Farmer John can perfectly distinguish his spotty cows from his plain cows. In this example, or indicates a spotty cow, while indicates a plain cow; is irrelevant because it does not occur in any of the cows at position .
Position , on the other hand, cannot explain spottiness by itself, since the character A occurs in both a spotty cow and a plain cow.
Given the genomes of Farmer John's cows, count the number of positions that could potentially explain spottiness by themselves.
The first line contains two positive integers and , both at most . The next lines each contain a string of characters describing the genome of a spotty cow. The final lines describe the genomes of the plain cows.
Print the number of positions (an integer in the range ) in the genome that could potentially explain spottiness. A position can explain spottiness if the spottiness trait can be predicted with perfect accuracy for all of Farmer John's cows by looking only at that position in the genome.
Example 1