Genomica bovina (Bronzo)#10522

Genomica bovina (Bronzo)

1 secondo

128 megabyte

Facile

L'agricoltore John ha $n$ mucche pezzate e $n$ mucche a tinta unita. Avendo recentemente completato un corso di genetica bovina, ha concluso che le macchie sulle sue mucche sono causate da una mutazione in un unico punto del genoma.

Dopo aver pagato una notevole somma di denaro, l'agricoltore John sequenzia i genomi di tutte le sue mucche. Ogni genoma è una stringa di lunghezza $m$ composta dai quattro caratteri $A$ , $C$ , $G$ e $T$ . Se allinea i genomi delle sue mucche uno sotto l'altro, ottiene una tabella simile alla seguente, mostrata per il caso $n = 3$ 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

Analizzando attentamente questa tabella, nota che la posizione $2$ potrebbe essere il sito che spiega la presenza delle macchie. In altre parole, guardando solo il carattere in quella posizione, l'agricoltore John può distinguere senza errori le mucche pezzate da quelle a tinta unita. In questo esempio, i caratteri $A$ o $G$ corrispondono alle mucche pezzate, mentre $C$ corrisponde a quelle a tinta unita; il carattere $T$ non ha importanza, poiché nessuna mucca presenta $T$ in posizione $2$ .

La posizione $1$ , invece, da sola non può spiegare la presenza delle macchie, poiché il carattere $A$ compare sia in una mucca pezzata che in una mucca a tinta unita.

Dati i genomi delle mucche, determina il numero di posizioni che, da sole, potrebbero spiegare la presenza delle macchie.

Input

La prima riga contiene due interi positivi $n$ e $m$ , entrambi non superiori a $100$ . Le successive $n$ righe contengono ciascuna una stringa di lunghezza $m$ che descrive il genoma di una mucca pezzata. Le ultime $n$ righe descrivono i genomi delle mucche a tinta unita.

Output

Stampa il numero di posizioni (un intero nell'intervallo $0.. m$ ) nel genoma che, da sole, potrebbero spiegare la presenza delle macchie. Una posizione può spiegare la presenza delle macchie se, guardando il carattere solo in quella posizione, è possibile determinare con certezza al cento per cento se una mucca è pezzata o a tinta unita, per tutte le mucche dell'agricoltore John.

Esempi

Esempio 1