说明

为了吸引更多游客来到巴黎，Anne 计划在卢浮宫的外墙举办一场盛大的声光秀。外墙上有多层窗户，且窗户在垂直方向上对齐。因此，Anne 想到通过窗户展示巨型字母，每个窗户一个字母，从而同时在水平和垂直方向上形成单词。

在给定的外墙上，窗户排列成一个 $N$ 行 $M$ 列的矩形网格。Anne 收集了一个包含 $A$ 个 $N$ 字母单词的列表和一个包含 $B$ 个 $M$ 字母单词的列表。她想知道有多少种方式在该网格上同时水平显示 $N$ 个长度为 $M$ 的单词和垂直显示 $M$ 个长度为 $N$ 的单词。

输入格式

输入包含以下内容：

• 第一行包含两个整数 $N$ 和 $A$，用一个空格分隔。
• 第二行包含两个整数 $M$ 和 $B$，用一个空格分隔。
• 接下来的 $A$ 行包含 $N$ 字母单词，每行一个。
• 接下来的 $B$ 行包含 $M$ 字母单词，每行一个。

输出格式

输出应包含一行，内容为一个整数，表示不同单词网格的总数。

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

2

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

2

提示

样例解释 1

解决方案如下：

样例解释 2

解决方案如下：

数据范围

输入满足 $2 \leq N, M \leq 4$ 且 $1 \leq A \times B \leq 1008016$。

单词来自英语词典。两个列表中的单词均不重复。单词由 'a'（ASCII 码 97）到 'z'（ASCII 码 122）的小写字母组成。

第一个列表中的单词将垂直显示，从上到下。第二个列表中的单词将水平显示，从左到右。同一个单词可以在构建网格时多次使用，即如果它属于第一个（或第二个）单词列表，它可以出现在多个列（或行）中。

当 $N = M$ 时，不允许将第一个列表中的单词水平使用（除非它们也出现在第二个列表中），也不允许将第二个列表中的单词垂直使用（除非它们也出现在第一个列表中）。

翻译由 DeepSeek 完成