Description

给定一个字符串T，并给出一个字符串组S

求S中的所有字符串在串T中出现的次数

Input Format

第一行一个字符串T， T.length() <= 1e7

第二行一个整数n <= 30，表示组S中字符串的个数

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

Output Format

按输入顺序依次输出组S中字符串及其在T中出现的次数

中间用空格隔开

xttxttxtt
3
x
xt
t

x 3
xt 3
t 6

Hint

Source

AC自动机