P15198 [SWERC 2018] Crosswords

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 $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.

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.

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

#### Sample Explanation 1 The solutions are: | s | a | y | s | |:-:|:-:|:-:|:-:| | a | r | e | a | | t | e | s | t | | w | a | y | s | |:-:|:-:|:-:|:-:| | a | r | e | a | | r | e | s | t | #### Sample Explanation 2 The solutions are: | i | t | s | |:-:|:-:|:-:| | t | h | e | | s | e | t | | r | a | n | |:-:|:-:|:-:| | a | g | o | | n | o | w | #### Limits The input satisfies $2 \leq N, M \leq 4$ and $1 \leq A \times B \leq 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).