Description

Pingping takes Yunyun to an amusement park and sees $n$ beautiful remote-controlled cars. Each car has a unique name name[i]. Yunyun has long wanted to play the car whose name is $s$. However, since Yunyun is still young, the name she imagines might be a prefix of some car’s name (that is, there exists an $i$ such that $s$ is a prefix of name[i]); in this case, she can play the $i$-th car. Or it might be a completely made-up name that is not a prefix of any car’s name; in that case, she cannot play anything.

You need to complete the following tasks:

1. Yunyun thinks of $m$ desired names. Tell her how many times she can play.

2. Due to the staff’s careless operation, each car’s placement may have a slight error: the original $i$-th car may now be at any one of the positions $i-1$, $i$, or $i+1$ (the position of the $1$-st car cannot be $0$, and the position of the $n$-th car cannot be $n+1$). Calculate how many possible permutations there are.

Note: The testdata guarantees that when $s$ is a prefix of name[i], the index $i$ is uniquely determined. A car can be played multiple times.

Input Format

The first line contains two positive integers $n$ and $m$.

The next $n$ lines each contain one string name[i], the name of the $i$-th car. Then the next $m$ lines each contain one string $s$, the name Yunyun wants.

Output Format

Output two lines:

• The first line contains the number of times Yunyun can play.
• The second line contains the number of possible permutations.

4 4
Abcd
DeF
AAa
aBccc
Ab
AA
AbC
aBcc

3
5

Hint

Note:

• All strings are strictly case-sensitive and have length less than $255$.

Constraints:

• For $20\%$ of the testdata, $n \le 10$, $m \le 10$.
• For $40\%$ of the testdata, $n \le 1000$, $m \le 1000$.
• For $100\%$ of the testdata, $n \le 10000$, $m \le 10000$.

Translated by ChatGPT 5