Background

AC自动机模板题

Description

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

Format

Input

第一行一个n，表示模式串个数；
下面n行每行一个模式串；
下面一行一个文本串。

Output

一个数表示ans。

Sample 1

Input

2
a
aa
aa

Output

2

Limitation

0.25s，512MB

Hint

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；
subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；