G - Unit testing

Time limit: 9 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

Fito está trabajando con un grupo de desarrolladores de software, en una herramienta para la recuperación de información. Como aún está empezando, le han asignado la tarea de crear pruebas unitarias para probar la herramienta. Una de las partes que está probando, se encarga de guardar todas las subcadenas de un texto. El método que Fito quiere probar recibe una cadena y si esta aparece en el texto, devuelve su índice en la lista de todas las subcadena en orden lexicográfico.

Para probar con mayor facilidad este código Fito quiere resolver el problema inverso: Dado el texto completo y el índice, buscar la subcadena correspondiente. Fito piensa hacer una colección de pruebas y por tanto para un mismo texto tiene varios índices que quiere buscar. Un detalle que no tiene muy claro de la implementación es, si en la lista de las subcadenas del texto hay repeticiones. Para estar seguro Fito decide buscar por cada índice las dos posibles subcadenas (contando las repetidas o solo las diferentes).

Input

La primera línea de la entrada es la cadena $S$, formado por letras minúsculas y su tamaño es menor o igual a $200000$. Después le sigue una línea con un entero $Q (1 \leq Q \leq 500)$ que indica la cantidad de preguntas que va a resolver Fito. Por cada pregunta hay un entero $K_i (1 \leq Ki \leq 10^6)$ en una línea que indica el índice de la subcadena buscada.

Output

Por cada pregunta se deben imprimir las dos posibles subcadenas. En la primera línea se imprime la subcadena con el índice dado si en la lista aparecen las subcadena repetidas. En la segunda línea, la subcadena buscada si solo se cuentan las diferentes. Si alguna subcadena no existe se debe imprimir “No existe.”

Sample test(s)

Input
aba 3 2 4 6
Output
a ab aba b ba No existe.