406627: GYM102465 C Crosswords

C. Crosswordstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output In order to attract more tourists in Paris, Anne wants to organize a huge sound and light show at night on the facades of the Louvre Palace. The facades are showing windows on several levels, and the windows are also vertically aligned. So Anne has the idea of displaying giant letters through the windows, one per window, so that it forms words both horizontally and vertically.

On a given facade, windows are organized on a rectangular grid with $$$N$$$ rows and $$$M$$$ columns. Anne has gathered a list of size $$$A$$$ of $$$N$$$-letter words and a list of size $$$B$$$ of $$$M$$$-letter words. She is wondering how many ways there are to display simultaneously $$$N$$$ words of length $$$M$$$ horizontally and $$$M$$$ words of length $$$N$$$ vertically on that grid.

Input

The input consists of the following:

• The first line contains two integers N and A separated with a single space.
• The second line contains two integers M and B separated with a single space.
• The next A lines contains N-letter words, one per line.
• The next B lines contains M-letter words, one per line.

Limits

The input satisfies $$$2 \le N$$$, $$$M \le 4$$$ and $$$1 \le A \times B \le 1008016$$$.

Words are taken from the English dictionary. Each of the two lists contains no repetition. Words consist of lowercase letters between 'a' (ASCII code 97) and 'z' (ASCII code 122).

Words from the first list will be displayed vertically, from top to bottom. Words from the second list will be displayed horizontally, from left to right. The same word can be used several times to build a grid, i.e., in several columns (resp., rows) if it belongs to the first (resp., second) list of words.

When $$$N = M$$$, it is not allowed to use words from the first list horizontally (unless they appear in the second list as well), or words from the second list vertically (unless they appear in the first list as well).

Output

The output should consist of a single line, whose content is an integer, the total number of distinct word grids.

ExamplesInput

3 4
4 5
war
are
yes
sat
says
area
test
ways
rest

Output

2

Input

3 7
3 7
ran
age
now
its
the
set
ago
ran
age
now
its
the
set
ago

Output

2

Note

Sample Explanation 1

The solutions are:

Sample Explanation 2

The solutions are: