单点时限: 2.0 sec
内存限制: 512 MB
If a string is the same as itself after reversion, it can be called a palindrome .
For example, abbcbba, bbb are palindromes and abab, abc are not palindromes.
Given are two sequcences of strings. The first sequence $A$ contains $n$ strings, $a_1,a_2\cdots a_n$. And the second sequence $B$ contains $m$ strings, $b_1,b_2\cdots b_n$.
Now, George wants to choose two integers $(i,j)$ ,where $1\le i\le n,1\le j\le m$. Then he will concatenate string $a_i$ and string $b_j$ to construct a new string “$a_i+b_j$” (where $a_i+b_j$ means to put string $b_j$ right after string $a_i$). For example, if $A={\text{h, ehe, jie}}$, $B={\text{ak, noi}}$ and he chooses $(1,2)$ , then he will construct a new string “$\text{hnoi}$” .
For this problem, you need to tell George that how many different integer pairs $(i,j)$ he can choose to construct a palindrome.
The first line contains an integer $n$, indicating that there are $n$ strings in sequence $A$.
In next $n$ lines, the $i$-th line contains a string $a_i$ indicating the $i$-th string of sequence $A$.
The next line contains an integer $m$, indicating that there are $m$ strings in sequence $B$.
In next $m$ lines, the $i$-th line contains a string $b_i$ indicating the $i$-th string of sequence $B$.
An integer, representing the number of different integer pairs $(i,j)\ \big(1\le i\le n,1\le j\le m\big)$ that makes “$a_i+b_j$” a palindrome.
2 ab aa 3 ba a ba
4
2 george plover 4 lenska danica groeg evolp
2
2 ababa aba 2 ba ab
2
The data guarantees that all strings are non-empty and that the sum of all strings’ lengths satisfy: $\sum |a_i| + \sum |b_i| \leq 10^6$.
All strings are composed of lowercase letters.
Sample 1 Explanation:
The $4$ pairs are:
| $(i,j)$ | Palindrome |
|---|---|
| $(1,1)$ | abba |
| $(1,2)$ | aba |
| $(1,3)$ | abba |
| $(2,2)$ | aaa |