Description

Given two sets of strings $\mathcal{S}$ and $\mathcal{T}$. All strings in $\mathcal{S}$ have length exactly $N$, and all strings in $\mathcal{T}$ have length exactly $M$. Moreover, $N + M$ is even.

If we denote all strings in $\mathcal{S}$ by $S_1, S_2, \dots, S_{Total_S}$, and all strings in $\mathcal{T}$ by $T_1, T_2, \dots, T_{Total_T}$, we want to know how many pairs $\langle i, j \rangle$ satisfy that the concatenation $S_i + T_j$ has the double rotation property.

An even-length string $W$ can be written as the concatenation of two strings of equal length, i.e., $W = U + V$. If $V$ can be obtained from $U$ by a rotation (cyclic shift), then $W$ is said to have the double rotation property. For example, the string vijos can be rotated to ijosv, josvi, osvij, or svijo. Thus, vijosjosvi has the double rotation property.

Input Format

The first line contains four positive integers $Total_S, Total_T, N, M$, denoting respectively the size of set $\mathcal{S}$, the size of set $\mathcal{T}$, the length of strings in $\mathcal{S}$, and the length of strings in $\mathcal{T}$.

The next $Total_S$ lines each contain a string $S_i$, $1 \le i \le Total_S$. Each string has length exactly $N$, and consists only of the 26 lowercase letters.

The next $Total_T$ lines each contain a string $T_i$, $1 \le i \le Total_T$. Each string has length exactly $M$, and consists only of the 26 lowercase letters.

Output Format

Output a single integer, the number of pairs $\langle i, j \rangle$ that satisfy the requirement.

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

6

Hint

For $10\%$ of the testdata, $1 \leq N \leq 100$, $1 \leq M \leq 100$, $1 \leq Total_S \leq 100$, $1 \leq Total_T \leq 100$.

For $30\%$ of the testdata, $1 \leq N \leq 500$, $1 \leq M \leq 500$, $1 \leq Total_S \leq 500$, $1 \leq Total_T \leq 500$.

For $60\%$ of the testdata, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^5$.

For $100\%$ of the testdata, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^6$.

Translated by ChatGPT 5