测试数据来自 system/1960

描述

给定两个字符串集合\(\mathcal{S}\)和$\(\mathcal{T}\)。其中\(\mathcal{S}\)中的所有字符串长度都恰好为N，而\(\mathcal{T}\)中所有字符串长度都恰好为M，且N+M恰好为偶数。

如果记\(\mathcal{S}\)中字符串全体为\(S_1,S_2,\cdots,S_{Total_S}\)，而\(\mathcal{T}\)中字符串全体为\(T_1,T_2,\cdots,T_{Total_T}\)。现在希望知道有多少对\(\langle i,j\rangle\)，满足将\(S_i\)和\(T_j\)拼接后得到的字符串\(S_i+T_j\)满足双旋转性。

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

格式

输入格式

第一行输入四个正整数，分别为\(Total_S\)，\(Total_T\)，N和M，依次表示集合\(\mathcal{S}\)的大小，集合\(\mathcal{T}\)的大小，集合\(\mathcal{S}\)中字符串的长度和集合\(\mathcal{T}\)中字符串的长度。

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

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

输出格式

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

样例1

样例输入1

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

样例输出1

6

限制

对于10%的数据，\(1\le N\le 100,~1\le M\le 100,~1\le Total_S\le 100,~1\le Total_T\le 100\)。
对于30%的数据，\(1\le N\le 500,~1\le M\le 500,~1\le Total_S\le 500,~1\le Total_T\le 500\)。
对于60%的数据，\(2\le N\times Total_S + M\times Total_T \le 4\times 10^5\)。
对于100%的数据，\(2\le N\times Total_S + M\times Total_T \le 4\times 10^6\)。

来源

SDOI2015 round2 day1