4555. Construct Palindrome String

单点时限: 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.

样例

Input
2
ab
aa
3
ba
a
ba
Output
4
Input
2
george
plover
4
lenska
danica
groeg
evolp
Output
2
Input
2
ababa
aba
2
ba
ab
Output
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

24 人解决,58 人已尝试。

27 份提交通过,共有 309 份提交。

6.5 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,11 月前.

最后提交: 1 年,4 月前.

来源: N/A

题目标签