- Time limit: 1.00 s
- Memory limit: 512 MB
The first input line has a string of length $n$.
The next input line has an integer $k$: the number of patterns. Finally, there are $k$ lines that describe the patterns.
The string and the patterns consist of characters a–z.
For each pattern, print the number of positions.
- $1 \le n \le 10^5$
- $1 \le k \le 5 \cdot 10^5$
- the total length of the patterns is at most $5 \cdot 10^5$