Remote Control Cars and Permutation Arrangements

You are given an amusement park scenario where there are n beautiful remote control cars. Each car has a unique name given by name[i] (1 ≤ i ≤ n). A little girl, YunYun, has m desired names. For each desired name s, if s is a prefix of some car's name, then she can play with that car. Note that it is guaranteed that if s is a prefix of some car name then the index i is uniquely determined. Otherwise, if s is not a prefix of any car name, she cannot play with any car. Your first task is to count how many times YunYun can play the cars.

The second task is related to a misplacement error. Due to the carelessness of the administrator, the positions of the cars might have shifted slightly. The car originally in position i can now be in any of the positions i-1, i, or i+1, with the restriction that the first car cannot be in position 0 and the last car cannot be in position n+1. You are required to compute the total number of valid arrangements (permutations) of cars that satisfy the above conditions.

Hint: For the second part, it can be shown that if we define f(1)=1, f(2)=2, and for n \ge 3, f(n)=f(n-1)+f(n-2), then f(n) is the number of valid arrangements.

Note on Prefix Uniqueness: The input guarantees that if a query string s is a prefix of a car name, then there is exactly one car whose name has s as its prefix.

inputFormat

The first line contains two integers n and m — the number of cars and the number of queries respectively.

The next n lines each contain a non-empty string name[i] representing the unique name of the i-th car. It is guaranteed that the names are chosen such that if a query string is a prefix of some car name, then it is a prefix of exactly one car name.

The following m lines each contain a non-empty string s — the desired name by YunYun.

outputFormat

Output two lines:

• The first line should contain a single integer denoting the number of times YunYun can play with a car (i.e. the number of queries for which s is a prefix of a car name).
• The second line should contain a single integer denoting the total number of valid arrangements of the cars.

sample

3 4
abc
def
ghi
ab
de
xy
gh

3
3