Problem
Blaze envía órdenes de movimiento a sus tropas, obtenidas de los habitantes de una de las sombras. Desafortunadamente, no entienden a Amber, por lo que Blaze tiene que enviarles mensajes en su propio idioma.
Ahí radica el problema: el príncipe ambarino no conoce bien la ortografía de este idioma, por lo que a veces comete errores en las palabras, pero no más de un error en una palabra.
Hay muchas palabras en el idioma, por lo que si al menos una letra de una palabra cambia, su significado puede cambiar drásticamente. Si el ejército no comprende correctamente la orden, toda la campaña militar puede fracasar. Por lo tanto, es muy importante que Blaise verifique la ortografía correcta de las palabras. Decidió pedirte que lo ayudaras.
Debe crear un programa que genere en orden lexicográfico todas las palabras posibles que Blaise podría haber intentado escribir, dado que podría haberse equivocado 1 vez.
Entrada < /i>
La primera línea contiene los números n y m: el número de órdenes dadas por Blaze y el número de comandos entendidos por sus tropas, respectivamente. (1 <= n, m <= 5000)
La siguiente línea toma m palabras como entrada: comandos que las tropas de Blaze entienden.
En las próximas n líneas, las palabras se dan como entrada: órdenes dadas por Blaze.
Todas las cadenas tienen menos de 100.
Salida < /i>
Imprime n líneas: el número de línea i contiene la respuesta al problema para el número de orden i de Blaze. Las líneas que son la respuesta a esta consulta se muestran en una sola línea separadas por un espacio.
Ejemplo
Entrada
5 5
está en si en de
es
en
de
i
op
Salida
si en es
si está activado
si de encendido
si en es
de el
(c) Evgeny Grigoriev