The Jedi Knight Guilherme
By Ezequiel Rodrigues da Silva, PUC Goiás 
Brazil
By Ezequiel Rodrigues da Silva, PUC Goiás Brazil
The Jedi Knight Guilherme and his companion R2-D2 are rescuing Chancellor Palpatine from Count Dooku. When Guilherme entered in the spaceship, Dookan blocked all the doors with a shield that not even a lightsaber can cut. R2-D2 quickly accessed the system of the ship in order to turn off the shield, but the system has a defense mechanism that, to break it, the following challenge must be answered: given a string S of size n and several other strings V1, V2, … , Vm, how many palindromic substrings s exist in S such that, for all 1 ≤ i ≤ m, Vi is not a substring of s? Since the string S is too large, Guilherme is using the Force to communicate and he asks you to make a program that solves this problem.
The input consists of several test cases and is finished by the end-of-file (EOF). The first line of each case contains two nonnegative integers n and m (1 ≤ n, m ≤ 100). The second line contains a string S string consisting of n alphanumeric characters. Each of the next m lines contains a string Vi (1 ≤ | Vi | ≤ 100) containing only alphanumeric characters.
For each test case, print a single line containing the answer to the challenge.
| Input Sample | Output Sample |
|
14 3 |
19 |