3 Bigyration

Given two sets of strings $S$ and $T$. All strings in $S$ have length $N$, and all strings in $T$ have length $M$, where $N+M$ is even. Let the strings in $S$ be $S_1, S_2, \dots, S_{Total_S}$, and the strings in $T$ be $T_1, T_2, \dots, T_{Total_T}$. We want to know how many pairs $(i, j)$ exist such that the concatenation of $S_i$ and $T_j$ satisfies the "bigyration" property. A string $W$ of even length is said to satisfy the "bigyration" property if $W$ can be represented as the concatenation of two strings of equal length, i.e., $W = U + V$, and $V$ can be obtained by rotating $U$. For example, if $U = \text{"vijos"}$, it can be rotated to obtain $\text{"ijosv"}$, $\text{"josvi"}$, $\text{"osvij"}$, or $\text{"svijo"}$. Thus, $\text{"vijosijosvi"}$ is a string that satisfies the bigyration property.

Input

The first line contains four integers: $Total_S$, $Total_T$, $N$, and $M$, representing the size of set $S$, the size of set $T$, the length of strings in $S$, and the length of strings in $T$, respectively. The next $Total_S$ lines each contain a string $S_i$ ($1 \le i \le Total_S$). It is guaranteed that each string has length $N$ and consists of 26 lowercase English letters. The next $Total_T$ lines each contain a string $T_i$ ($1 \le i \le Total_T$). It is guaranteed that each string has length $M$ and consists of 26 lowercase English letters.

Output

Output a single integer representing the number of pairs $(i, j)$ that satisfy the requirements.

Constraints

• For 10% of the data, $1 \le N \le 100$, $1 \le M \le 100$, $1 \le Total_S \le 100$, $1 \le Total_T \le 100$.
• For 30% of the data, $1 \le N \le 500$, $1 \le M \le 500$, $1 \le Total_S \le 500$, $1 \le Total_T \le 500$.
• For 60% of the data, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^5$.
• For 100% of the data, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^6$.

Examples

Input 1

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

Output 1

6