Migrated from Lutece 3070 数据攻防1

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你是黑塔空间站的网络安全员，在检查空间站内的网络安全情况时，你发现了那位入侵空间站的神秘骇客留下的记号。你尝试解码了一小段数据，似乎是一条留言，上面显示：防火墙就这？

这让你有了一丝不妙的预感。为了排除安全隐患，你决定先将所有的标记找出来。通过搜集数据，你得到了 $n$ 条可疑讯息 $T_{1\sim n}$，每条讯息为一个只包含小写字母 $a$ 到 $z$ 的字符串。现在，你从空间站中截取了一段长度为 $|S|$ 的数据，$S$ 同样为只包含小写字母 $a$ 到 $z$ 的字符串，请分别求出每条可疑讯息 $T_i$ 在 $S$ 中出现的次数。

Input

第一行一个整数 $n$，表示可疑讯息数量。

第二至 $n+1$ 行，每行一个字符串表示一条可疑讯息，字符串只包含小写字母 $a$ 到 $z$。

第 $n+2$ 行为一个字符串，表示待检查的数据串 $S$，$S$ 只包含小写字母 $a$ 到 $z$。

Output

输出 $n$ 行，第 $i$ 行为一个整数表示第 $i$ 条可疑讯息在字符串 $S$ 中出现的次数。

Samples

5
a
bb
aa
abaa
abaaa
abaaabaa

6
0
3
2
1

Constraints

$1\leq n \leq 2\times 10^5$， $T_{1\sim n}$ 的总长 $\sum{|T_i|}\leq 2\times 10^5$， $S$ 的长度 $|S|\leq 2\times 10^6$

Resources

2023 UESTC ICPC Training for String