Description

There is a street consisting of $N$ lowercase English letters. The city government occasionally replaces the tiles on the street. However, letter tiles are in high demand, so the government only has $M$ kinds of letter tiles to choose from.

The pattern of the $i$-th tile consists of $L_{i}$ letters. Tiles cannot be rotated or broken, and they can only be placed where the tile’s letters exactly match a contiguous substring of letters on the street.

Tiles may overlap, and multiple tiles with the same pattern may be used. If a street cannot be covered by any tiles, then it is bad.

Find how many bad streets there are.

Input Format

The first line contains an integer $N$, the number of letters on the street.

The second line contains $N$ lowercase letters, the sequence on the street.

The third line contains an integer $M$, the number of tiles.

The next $M$ lines each contain $L_{i}$ lowercase letters, describing the pattern of that tile.

Output Format

Print one line with an integer, the number of bad streets.

6
abcbab
2
cb
cbab

2

4
abab
2
bac
baba

4

6
abcabc
2
abca
cab

1

Hint

Constraints: $1\le N\le 3\times 10^{5}$, $1\le M\le 5\times 10^{3}$, $1\le L_{i}\le 5\times 10^{3}$.

Translated from COCI 2011/2012 #5 T6.

Translated by ChatGPT 5