아호 코라식

알파벳 소문자로 이루어진 패턴 문자열 $P$개와 텍스트 문자열 $S$가 주어진다. 각 패턴이 $S$ 안에 등장하는 횟수를 출력하여라. 등장은 시작 위치가 다르면 서로 다른 등장으로 세며, 서로 겹칠 수 있다. 같은 패턴 문자열이 여러 번 입력될 수 있고, 이 경우 각 패턴의 답을 각각 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$P$ $W_1$ $W_2$ $\vdots$ $W_P$ $S$

첫째 줄에 $P$개의 정수를 출력한다. $i$번째 정수는 $W_i$가 $S$에 등장하는 횟수이다.

• $1 \leq P \leq 200\ 000$.
• $1 \leq |W_i|$ ($1 \leq i \leq P$).
• $1 \leq |S|$.
• $\sum_{i=1}^{P}|W_i|+|S| \leq 500\ 000$.
• 모든 문자열은 알파벳 소문자로만 이루어진다.