Dada una cadena y patrones, encuentra para cada patrón la primera posición (indexada desde 1) donde aparece en la cadena.

Entrada

• La primera línea de entrada contiene una cadena de longitud ~n~.
• La siguiente línea de entrada contiene un entero ~k~: el número de patrones. Finalmente, hay ~k~ líneas que describen los patrones.

La cadena y los patrones constan de caracteres de la a a la z.

Salida

Imprime la primera posición de cada patrón (o -1 si no aparece).

Restricciones

• ~1 \leq n \leq 10^5~
• ~1 \leq k \leq 5 \cdot 10^5~
• La longitud total de los patrones es como máximo ~5 \cdot 10^5~.

Ejemplo de Entrada

aybabtu
3
bab
abc
a

Ejemplo de Salida

3
-1
1