Description

We define a string consisting of lowercase letters and question marks as a parameterized word. For example, a??cd, bcd, and ?? are all parameterized words.

If, for two parameterized words, we can replace the question marks in each of them with specific lowercase letters so that the two resulting words become exactly the same, then the two original parameterized words are called similar. For example, both a??? and ?b?a can be replaced to become abba, so a??? and ?b?a are similar.

Given $N$ parameterized words of length $M$, find how many pairs of parameterized words are similar.

Input Format

The first line contains integers $N, M$.

The next $N$ lines each contain a parameterized word of length $M$.

Output Format

Output the number of pairs of similar parameterized words.

3 3
??b
c??
c?c

2

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

3

5 2
??
b?
c?
?g
cg

8

Hint

Explanation for Sample 1

??b and c?? are similar, and c?? and c?c are also similar. Therefore, there are a total of $2$ pairs of similar parameterized words.

Constraints

For $30\%$ of the testdata, $M \le 2$.

For another $30\%$ of the testdata, $M \le 4$.

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4$ and $1 \le M \le 6$.

Notes

The score settings of this problem follow the original COCI problem, with a full score of $110$.

This problem is translated from COCI2018-2019 CONTEST #5 T4 Parametriziran.

Translated by ChatGPT 5