题目描述

裸AC自动机
给定一个字符串T，并给出一个字符串组S
求S中的所有字符串在串T中出现的次数

输入格式

第一行一个字符串T T.length() <= 1e7
第二行一个整数n <= 30，表示组S中字符串的个数
接下来n行每行一个字符串，第i行表示组S中的字符串 Si Si.length() <= 20

输出格式

按输入顺序依次输出组S中字符串及其在T中出现的次数
中间用空格隔开

样例

####样例输入

xttxttxtt
3
x
xt
t

####样例输出

x 3
xt 3
t 6

数据范围与提示

n <= 30
T.length() <= 1e7
Si.length() <= 20