Background

When you look into a mirror, do you notice the things behind you? I believe most people's focus is on their own virtual image.

Now imagine a mirror where you can see all your possible current states or futures; perhaps some version of you is living a life similar to your friend's. You might find an idealized self in the mirror, perhaps the person you are now, or a better version of yourself. But just like the background in the mirror, there are many possibilities where other versions of you are not as lucky, living more ordinary or harder lives. What remains unchanged, however, is that all these possibilities are still you. From the very beginning, you have possessed wings capable of turning possibilities into reality.

Do not ignore every detail in the mirror. When you shatter this mirror, you will obtain a complete pair of wings. Break free from all constraints, push off the ground, and spread your wings to fly.

Description

Given a sequence of strings $S$ of size $n$ and a sequence of strings $T$ of size $m$, where the $i$-th string of $S$ is $S_i$ and the $j$-th string of $T$ is $T_j$.

Define the weight of a string $f(s)$ as the radius length of the longest odd-length palindromic substring in $s$. For example, the radius length of aba is 2, and the radius length of ababa is 3.

Define the addition of two strings $s+t$ as the new string obtained by concatenating the two strings.

Calculate $\displaystyle\sum_{i=1}^n \sum_{j=1}^m f(S_i+T_j)$.

Examples

Input 1

3 3
a
aba
aaba
b
ba
ab

Output 1

19

Note

The values of $f(S_i+T_j)$ for each pair $(i, j)$ are: - $f(S_1+T_1) = f(\text{"ab"}) = 1$ - $f(S_1+T_2) = f(\text{"aba"}) = 2$ - $f(S_1+T_3) = f(\text{"aab"}) = 1$ - $f(S_2+T_1) = f(\text{"abab"}) = 2$ - $f(S_2+T_2) = f(\text{"ababa"}) = 3$ - $f(S_2+T_3) = f(\text{"abaaab"}) = 2$ - $f(S_3+T_1) = f(\text{"aabab"}) = 2$ - $f(S_3+T_2) = f(\text{"aababa"}) = 3$ - $f(S_3+T_3) = f(\text{"aabaaab"}) = 3$ Sum = $1+2+1+2+3+2+2+3+3 = 19$.

Constraints

Let $s=\max(\sum|S_i|,\sum|T_i|)$.

This problem has 4 subtasks. You must pass all data in a subtask to receive the points for it.

For 100% of the data, $1 \le n,m,s \le 4\times10^5$, and it is guaranteed that the input strings only contain lowercase letters.