The amount of information on the World Wide Web is growing quite rapidly. In this information explosion age, we must survive by accessing only the Web pages containing information relevant to our own needs. One of the key technologies for this purpose is keyword search. By using well-known search engines, we can easily access those pages containing useful information about the topic we want to know.
There are many variations in keyword search problems. If a single string is searched in a given text, the problem is quite easy. If the pattern to be searched consists of multiple strings, or is given by some powerful notation such as regular expressions, the task requires elaborate algorithms to accomplish efficiently.
In our problem, a number of strings (element strings) are given, but they are not directly searched for. Concatenations of all the element strings in any order are the targets of the search here.
For example, consider three element strings aa, b and ccc are given. In this case, the following six concatenated strings are the targets of the search, i.e. they should be searched in the text.
The input consists of a number of datasets, each giving a set of element strings and a text. The format of a dataset is as follows.
n m
e1
e2
.
.
.
en
t1
t2
.
.
.
tm
For each dataset in the input, one line containing the number of matched positions should be output. An output line should not contain extra characters.
3 1 aa b ccc aabccczbaacccbaazaabbcccaa 3 1 a b c cbbcbcbabaacabccaccbaacbccbcaaaccccbcbcbbcacbaacccaccbbcaacbbabbabaccc 3 4 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 0 0
5 12 197
Although the sample input contains only small datasets, note that 12! × 5000 is far larger than 231.