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 parameterized words. Among the
Input
The first line contains the integer numbers
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
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