Migrated from Lutece 2645 樱之刻

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$ 条，每条为一个只由小写字母组成的字符串 $s_i$，检测题的那段文字 $t$ 也同样只由小写字母组成。

Input

第一行一个 $n$，表示字典条目数。 接下来 $n$ 行，每行为 $s_i$。 最后一行为检测题文本 $t$。

Output

输出 $n$ 个整数，表示 $s_i$ 在 $t$ 中作为字串出现过的次数。

Samples

3
what
is
mind
thisisnotmind

0
2
1

Constraints

$1\le n\le 2\times 10^5$ $1\le \sum{|s_i|}\le 2\times 10^5$ $1\le |t|\le 2\times 10^6$

所有字符串只包含小写字母。

Resources

2021 UESTC ICPC Training for String and Search Algorithm