Геноміка великої рогатої худоби (Бронза)#10522

Геноміка великої рогатої худоби (Бронза)

1 секунда
128 мегабайтів
Легка

Фермер Джон має плямистих корів та однобарвних корів. Нещодавно завершивши курс з генетики великої рогатої худоби, він дійшов висновку, що плями на його коровах спричинені мутацією в одному-єдиному місці геному.

Заплативши значну суму, Фермер Джон секвенує геноми всіх своїх корів. Кожен геном являє собою рядок довжини , що складається з чотирьох символів: A, C, G та . Якщо розташувати геноми його корів один під одним, вийде таблиця, подібна до наведеної нижче для випадку 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 ... T

Уважно вивчивши цю таблицю, він помічає, що позиція може бути місцем, яке пояснює наявність плям. Іншими словами, дивлячись лише на символ у цій позиції, Фермер Джон може безпомилково відрізнити плямистих корів від однобарвних. У цьому прикладі символи або відповідають плямистим коровам, а — однобарвним; символ не має значення, оскільки жодна з корів у позиції його не має.

Позиція , навпаки, сама по собі не може пояснити наявність плям, оскільки символ зустрічається як у плямистої, так і в однобарвної корови.

За заданими геномами корів визначте кількість позицій, які самі по собі можуть пояснити наявність плям.

Вхідні дані

У першому рядку містяться два додатних цілих числа та , що не перевищують . Наступні рядків містять по одному рядку довжини , що описує геном плямистої корови. Останні рядків описують геноми однобарвних корів.

Вихідні дані

Виведіть кількість позицій (ціле число в діапазоні ) у геномі, які самі по собі можуть пояснити наявність плям. Позиція може пояснити наявність плям, якщо за символом лише в цій позиції можна зі стовідсотковою точністю визначити, чи є корова плямистою, чи однобарвною, для всіх корів Фермера Джона.

Приклади

Приклад 1

Loading
Loading