문제

Author: Filip Pavetić

Mirko‟s ASCII street is made of N lowercase letters of the English alphabet. The city government occasionally replaces the tiles in the street. However, the letter tiles are in high demand, so the government has only M different tile patterns available. The ith tile pattern consists of Li letters. A tile cannot be rotated or broken into pieces, and it can only be placed such that the tile letters coincide with the contiguous letter subsequence in the street. Tiles can overlap and we can use multiple tiles of the same pattern. A street cell is untileable if it cannot be covered by any tile. Compute the number of untileable cells.

입력

The first line of input contains the positive integer N (1 ≤ N ≤ 300 000), the length of the street. The second line of input contains N lowercase English letters, the letter sequence in the street. The third line of input contains the positive integer M (1 ≤ M ≤ 5000), the number of tile patterns. Each of the next M lines contains a description of a tile pattern with length Li (1 ≤ Li ≤ 5000). The tile pattern descriptions consist of lowercase English letters.

출력

The first and only line of output must contain the required number of untileable cells.

예제 입력 1

6
abcbab
2
cb
cbab

예제 출력 1

2

예제 입력 2

4
abab
2
bac
baba

예제 출력 2

4

예제 입력 3

6
abcabc
2
abca
cab

예제 출력 3

1