You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

听说你们都会卷积神经网络？让我们一起来全连接吧。

题目背景

社长无意中听到，你们都会一堆的机器学习算法，特别是神经网络，很多同学都为此发表了相关的论文和专利。听到这里啊，社长不由得担心毕业后与谁抢工作的问题了。

题目描述

在卷积神经网络中，有着这样的一个结构：”全连接层“。在全连接层中，会提取目标的特征并进行分类，但是由于这个板块太难了，所以社长简化了全连接的过程。

1. 首先社长帮你们将原本的图像信息，按照行展开，并使用一个字符串来描述每一行的信息。
2. 输入另一个特征图像信息，并计算原图像中有多少个图像信息。

简单地来说，就是给你n个字符串s，每个字符串中间用空格隔开。然后再给你m个字符串t，同样每个字符串之间用空格隔开，在s中查找t的个数。

注意：在字符串匹配时们需要字符串全匹配上即可，比如:

在aa aaa aaaa查找aa aaa的个数的时候，只有'aa aaa' 这部分才能算匹配上。

输入

第一行输入字符串s( |s|<=$10^6$ )，表示原序列。

第二行输入一个正整数n，表示需要查找的字串t的数量。

接下来的n行，每行输入一个子字串t

输出

共n行，每行表示字串在原串中找到的次数。

样例

aa aa aa aaa
2
aa aa
aa aaa

2
1

数据范围

1<=n<=$4*10^5$

1<=m<=$4*10^5$

对于每个字符串的长度，均小于$10^5$

对于所有输入的字符数量和，小于等于$10^7$