题目背景

注意：本题相对于原题缩小了空间限制，需要一些小技巧才能通过。

题目描述

有一条由 $N$ 个英文小写字母组成的街道，市政府偶尔会更换街道上的瓷砖。但是，字母瓷砖的需求量很大，所以政府只有 $M$ 种字母瓷砖可供选择。

第 $i$ 个瓦片图案由 $L_{i}$ 个字母组成。瓷砖不能旋转，也不能打碎，而且只能放置在瓷砖字母与街道上连续的字母子序列重合的地方。

瓷砖可以重叠，且可以使用相同图案的多块瓷砖。如果一个街道不能被任何瓷砖覆盖，那么他就是不好的。

求有多少个不好的街道。

输入格式

第一行，一个整数 $N$，表示街道上的字母数。

第二行有 $N$ 个小写字母，表示街道上的序列，由小写字母组成。

第三行，一个整数 $M$，表示瓷砖数量。

接着 $M$ 行，每行 $L_{i}$ 个小写字母，表示该瓷砖的图案。

输出格式

一行，一个整数，表示方案数。

6
abcbab
2
cb
cbab

2

4
abab
2
bac
baba

4

6
abcabc
2
abca
cab

1

提示

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

题目译自 COCI 2011/2012 #5 T6。