Problem E
Popločavanje

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 $L_ i$ 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.

Input

The first line of input contains the positive integer $N$ ($1 \le N \le 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 \le M \le 5000$), the number of tile patterns.

Each of the next $M$ lines contains a description of a tile pattern with length $L_ i$ ($1 \le L_ i \le 5\, 000$). The tile pattern descriptions consist of lowercase English letters.

The total length of the tile patterns (the sum of the $L_ i$’s) is at most $13\, 000\, 000$.

Output

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

6
abcbab
2
cb
cbab

2

4
abab
2
bac
baba

4

6
abcabc
2
abca
cab

1