题目描述

给定两个字符串集合 $S$ 和 $T$ 。其中 $S$ 中的所有字符串长度都恰好为 $N$ ，而 $T$ 中所有字符串长度都恰好为 $M$ 。且 $N+M$ 恰好为偶数。如果记 $S$ 中字符串全体为 $S_1,S_2,\ldots,S_{TotalS}$ ,而 $T$ 中字符串全体为 $T_1,T_2,\ldots,T_{TotalT}$ 。现在希望知道有多少对 $(i,j)$ ，满足将 $S_i$ 和 $T_j$ 拼接后得到的字符串 $S_i+T_j$ 满足双旋转性。

一个长度为偶数字符串 $W$ 可以表示成两段长度相同的字符串的拼接，即 $W=U+V$。如果 $V$ 可以通过 $U$ 旋转得到，则称 $W$ 是满足双旋转性的。比如说字符串 $U=$ vijos 可以通过旋转得到 ijosv，josvi，osvij 或svijo。那么vijosjosvi 就是满足双旋转性的字符串。

输入格式

第一行输入四个正整数，分别为 $TotalS$，$TotalT$，$N$ 和 $M$，依次表示集合 $S$ 的大小，集合 $T$ 的大小，集合 $S$ 中字符串的长度和集合 $T$ 中字符串的长度。

之后 $TotalS$ 行，依次给出 $S$ 中所有的字符串 $S_i(1 \le i \le TotalS)$。保证每一个字符串长度都恰为 $N$ ，且字符串只由 $26$ 个小写字母组成。

之后 $TotalT$ 行，依次给出 $T$ 中所有的字符串 $T_i(1 \le i \le TotalT)$。保证每一个字符串长度都恰为 $M$，且字符串只由 $26$ 个小写字母组成。

输出格式

输出一个整数，表示满足要求的数字对 $(i,j)$ 有多少个。

4 4 7 3
vijosvi
josvivi
vijosos
ijosvsv
jos
vij
ijo
jos

6

样例分析

如上所述。

数据范围与提示

• 对于 $100\%$ 的数据：$1 \le N \le 100$，$1 \le M \le 100$，$1 \le TotalS \le 100$，$1 \le Total^T \le 100$ ， $2 \le N *TotalS+M *TotalT \le 4 \times 10^6$。