Mirko 的 ASCII 街道由 $N$ 个英文小写字母组成。市政府偶尔会更换街道上的瓷砖。然而，由于字母瓷砖非常紧俏，市政府只有 $M$ 种不同的瓷砖图案。

第 $i$ 种瓷砖图案由 $L_i$ 个字母组成。瓷砖不能旋转或拆分，且只能放置在与街道中连续字母子串完全一致的位置。

瓷砖可以相互重叠，且同一种图案的瓷砖可以使用多次。

如果街道的某个位置无法被任何瓷砖覆盖，则称该位置是无法铺设的。求无法铺设的街道位置数量。

输入格式

第一行包含一个正整数 $N$ ($1 \le N \le 300\,000$)，表示街道的长度。

第二行包含 $N$ 个英文小写字母，表示街道上的字母序列。

第三行包含一个正整数 $M$ ($1 \le M \le 5000$)，表示瓷砖图案的数量。

接下来的 $M$ 行，每行包含一个长度为 $L_i$ ($1 \le L_i \le 5000$) 的瓷砖图案描述。瓷砖图案描述由英文小写字母组成。

输出格式

输出的第一行也是唯一的一行，应包含无法铺设的街道位置数量。

样例

输入 1

6
abcbab
2
cb
cbab

输出 1

2

输入 2

4
abab
2
bac
baba

输出 2

4

输入 3

6
abcabc
2
abca
cab

输出 3

1