Annettuna on merkkijono sekä joukko haettavia merkkijonoja. Tehtäväsi on ilmoittaa jokaisesta haettavasta merkkijonosta sen ensimmäinen esiintymiskohta.

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 ensimmäinen esiintymiskohta (tai -1, jos se ei esiinny lainkaan).

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:

3
-1
1