Codah ClubВежбај. Пошаљи. Напредуј.
Пријави се
Српски
#00065A

POPLOCAVANJE - COCI

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 i-th 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.



InputThe 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.


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



Input:
6
abcbab
2
cb
cbab
Output:
2



Input:
4
abab
2
bac
baba
Output:
4



Input:
6
abcabc
2
abca
cab
Output:
1

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.