CSES - Hakeminen II
  • Time limit: 1.00 s
  • Memory limit: 512 MB
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