Problem Background

Note: This problem has reduced space constraints compared to the original, requiring some techniques to pass.

Problem Description

There is a street composed of $N$ lowercase English letters, and the city council occasionally replaces the tiles on the street. However, due to high demand for letter tiles, the government only has $M$ types of letter tiles available.

The $i$-th tile pattern consists of $L_{i}$ letters. Tiles cannot be rotated or broken, and can only be placed where the tile letters match a continuous subsequence of letters on the street.

Tiles can overlap and multiple tiles of the same pattern can be used. If a street cannot be covered by any tiles, it is considered bad.

Determine how many bad streets there are.

Input Format

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

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

The third line contains an integer $M$, representing the number of tile types.

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

Output Format

A single line containing an integer, representing the number of bad streets.

Sample Input and Output

Sample Input #1

6
abcbab
2
cb
cbab

Sample Output #1

2

Sample Input #2

4
abab
2
bac
baba

Sample Output #2

4

Sample Input #3

6
abcabc
2
abca
cab

Sample Output #3

1

Notes

$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}$.

The problem is translated from COCI 2011/2012 #5 T6.

见题面 Input 部分

见题面 Output 部分