COCI '18 Contest 5 #4 Parametriziran

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 64M

Problem type

A string of characters consisting of lowercase letters of the English alphabet and question marks is called a parameterized word (e.g., a??cd, bcd, ??). Two parameterized words are considered similar if the question mark symbols in both words can be replaced by arbitrary lowercase letters of the english alphabet so that the resulting strings are the same. For example, parameterized words a??? and ?b?a are similar because by replacing the question marks in both words it is possible to obtain the word abba.

Mirko has recently bought a collection of parametrized words. Among the N words found in the collection, Mirko is interested in how many pairs of similar parameterized words exist. All the words in the collection have the same number of characters, M, and it is possible that a word occurs multiple times in the collection.

Input

The first line contains the integer numbers N (1 \le N \le 50\,000) and M (1 \le M \le 6). Each of the following N lines contains one parameterized word from the collection with exactly M characters.

Output

Print the total number of similar pairs of parameterized words.

Scoring

In the test samples totally worth 30% of the points it will be valid M \le 2. In the test samples totally worth additional 30% points it will be valid M \le 4.

Sample Input 1

3 3
??b
c??
c?c

Sample Output 1

2

Explanation for Sample Output 1

Pairs of similar words are: (??b, c??) and (c??, c?c).

Sample Input 2

4 6
ab??c?
??kll?
a?k??c
?bcd??

Sample Output 2

3

Sample Input 3

5 2
??
b?
c?
?g
cg

Sample Output 3

8

Comments

There are no comments at the moment.