- Time limit: 1.00 s
- Memory limit: 512 MB
You are given a string and a list of words. For each word, your task is to count the number of occurrences in the string.
Input
The first line contains a string of length n that consists of characters A–Z.
The next line contains an integer w: the number of words.
Finally, there are w lines, each of which contains a word that consists of characters A–Z. The total length of the words is at most m.
Output
For each word, output the number of occurrences in the string.
Constraints
- 1 \le n,m \le 10^5
Example
Input:
AYBABTU 3 YBAB B XXX
Output:
1 2 0