Annettuna on merkkijono sekä joukko haettavia merkkijonoja. Tehtäväsi on ilmoittaa jokaisesta haettavasta merkkijonosta sen esiintymien määrä.

Syöte

Syötteen ensimmäisellä rivillä on merkkijono, jossa on n merkkiä.

Seuraavalla rivillä on kokonaisluku k: haettavien merkkijonojen määrä. Tämän jälkeen on k riviä, jotka kuvaavat merkkijonot.

Kaikki merkkijonot muodostuvat merkeistä a...z.

Tuloste

Ilmoita jokaisesta haettavasta merkkijonosta sen esiintymien määrä.

Rajat

• 1 \le n \le 10^5
• 1 \le k \le 5 \cdot 10^5
• haettavien merkkijonojen yhteispituus on enintään 5 \cdot 10^5

Esimerkki

Syöte:

aybabtu
3
bab
abc
a

Tuloste:

1
0
2