ASCII Street

The ASCII Street in front of Sanggeun's house consists of N tiles, each marked with a lowercase English letter. For unknown reasons, the government often replaces the street tiles. Because the supply of lettered tiles cannot keep up with demand, only M types of bundled tiles are available.

The i-th bundled tile contains Li letters. A bundled tile cannot be rotated or split into pieces. It can be used only when its letters exactly match a consecutive segment of the street. Replacement segments may overlap, and the same bundled tile may be used multiple times.

Given the current street string and all available bundled tiles, find how many street positions cannot be replaced by any bundled tile.

The first line contains the street length N. The second line contains the current lowercase English letter string written on the street. The third line contains the number M of bundled tile types. Each of the next M lines contains one lowercase English letter string written on a bundled tile.

The constraints are:

• 1 ≤ N ≤ 300,000
• 1 ≤ M ≤ 5,000
• 1 ≤ length of each bundled tile ≤ 5,000

Print the number of street positions that cannot be replaced by any bundled tile.