407633: GYM102861 L Lavaspar

Word Search is a well-known hobby, although it is losing some of its prestige in recent years. The goal in this game is to find words in an array, where each cell in this matrix contains a letter.

Bibika and her brother were playing Word Search, but soon they lost interest in the game, as finding all the words was getting relatively easy. Bibika would like to take her brother away from the computer, she searched the internet for games of the same style and ended up finding the Lavaspar Hunting.

Lavaspar Hunting is a game that follows the same idea of the famous Word Search. However, instead of simply having to find a word in the matrix, the goal is to find any anagram of the word, making the game more difficult and interesting. The anagram can be found in a row, column or diagonal.

An anagram is a word formed by rearranging the letters of another. Sometimes, an anagram does not exist as a word in the language, but this does not matter. balo, loba and aolb are examples of anagrams of the word bola.

Bibika realized that it was possible for the same cell in the matrix to make part of anagrams of different words and then she started to call these special cells.

Now she would like to know, given an array configuration and a collection of words, how many special cells are there?

The picture above illustrates the first example, where the collection of words consists of three words: bola, casa and boi. The rectangles of each color represent anagrams of different words from the entry. The $$$3$$$ special cells are painted yellow.

The first line contains two integers, $$$L$$$ and $$$C$$$, which correspond to the number of lines and columns of the array, respectively.

Each one of the next $$$L$$$ lines contains a word with $$$C$$$ letters.

These lines are followed by a line containing an integer, $$$N$$$, which is the number of words in the collection of words to follow.

Finally, there are now $$$N$$$ lines, each of which contains a word in the collection.

All characters in the array and in each word of the collection of words is a capital letter of the English alphabet.

No two of the $$$N$$$ words in the collection are anagrams of each other.

• $$$2 \le L, C \le 40$$$.
• $$$2 \le N \le 20$$$.
• The number $$$P$$$ of letters of each of the $$$N$$$ words is in the interval $$$2 \le P \le \min(15, \max(L, C))$$$.

The output consists of a single line that contains an integer corresponding to the number of special cells.

4 5
XBOIC
DKIRA
ALBOA
BHGES
3
BOLA
CASA
BOI

3

3 3
AAB
ABA
BAA
2
ABA
BBB

3

2 4
AAAA
AAAA
2
AAA
BBB

0