Compound
The mother of mouse Stofl is a very busy mouse. She is working in an executive position of a big cheese production company. Therefore she often has to attend important meetings and discussions. During these meetings many imposing words are used that sound important.
Often mouse Stofl does not understand what these terms mean and so he started to analyze them. Stofl discovered that all of these terms are composed of two parts – from a beginning of a word and an ending of a word that are then combined together to form the term. He possesses the complete list of all the possible word beginnings and word endings. He would like to find out, how many terms can be built from these two lists. Note that the two parts are just concatenated and not merged in any way, even in case of overlapping beginnings and endings.
Task
You are given two lists of words, one list with beginnings of words and one list with endings of words. Calculate the number of different words one can build by combining one word from the list with the word beginnings and one word from the list with the word endings. If the same word can be built with several different combinations, it should only be counted once. Please note that this task is case-sensitive, which means that two words like 'beginningEnd' and 'beginningend' are different.
Input
The first line of the input contains a single integer $A$ – the number of words in the list of word beginnings.
Each of the following $A$ lines contains a single string consisting of upper and lower case letters of the English alphabet ('A' to 'Z' and 'a' to 'z' respectively).
The $(A+2)$-th line contains a single integer $B$ – the number of words in the list of word endings.
Each of the following $B$ lines contains a single string consisting of upper and lower case letters of the English alphabet ('A' to 'Z' and 'a' to 'z' respectively).
You may assume that the length of each of the strings in the lists is not larger than $L$ which is specified in the «limits» section.
Output
Print a single integer – the number of different words combined from word beginnings and word endings as described above.
Limits
- For testcases worth 40% of the points, it holds that $1 \le A, B \le 100$ and $L \le 10$.
- For testcases worth 90% of the points, it holds that $1 \le A, B \le 10\,000$ and $L \le 15$.
- For testcases worth 100% of the points, it holds that $1 \le A, B \le 50\,000$ and $L \le 100$.
Example 1
| Input | Output | |
2 Geld Geldau 2 tomaten automaten |
3 |
One can build Geldtomaten, Geldautomaten and Geldauautomaten, where Geldautomaten can be composed in two different ways.
Example 2
| Input | Output | |
6 Organisations Identifikations Drittgenerations Koalitions Fluktuations Wachstums 9 struktur ebene tendenz programmierung konzeption phase kritik problematik kontingenz |
54 |
Submission
