Conteggio dei Pattern#2604

Conteggio dei Pattern

1 secondo
128 megabyte

Data una stringa e un insieme di pattern, determinare per ciascun pattern il numero di posizioni in cui esso compare nella stringa.

Input

La prima riga contiene una stringa di lunghezza n~(1 \le n \le 10^5).

La seconda riga contiene un intero k~(1 \le k \le 5 \cdot 10^5) — il numero di pattern. Ciascuna delle successive righe contiene un pattern. La lunghezza totale di tutti i pattern non supera 5 \cdot 10^5.

La stringa e i pattern sono costituiti da lettere latine minuscole '' - ''.

Output

Per ciascun pattern, stampare su una riga separata il numero delle sue occorrenze nella stringa.

Esempi

Esempio 1

Loading
Loading