Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

En la clase de Probabilidad dejaron como tarea un ejercicio interesante. Si Fito es capaz de hacerlo puede convalidar el examen final. El ejercicio pide calcular las probabilidades de las longitudes y cantidad de ocurrencias de las subcadenas de un texto. Fito no es muy bueno en probabilidades y quiere hacer algunos ejemplos para tratar de encontrar alguna idea que le permita resolver el ejercicio.

Cada ejemplo de Fito consiste en un texto generado de forma aleatoria que solo contiene letras minúsculas del alfabeto latino. Después Fito calcula la probabilidad de algunos pares de valores correspondientes a la longitud y cantidad de ocurrencias. Fito calcula la probabilidad como la cantidad de subcadenas diferentes, que tienen determinada longitud y cantidad de ocurrencias sobre la cantidad total de subcadenas diferentes. Para él es fácil contar la cantidad de subcadenas diferentes en un texto, el problema es la otra parte. Necesita, por tanto, que lo ayudes a calcular para un texto de ejemplo las cantidades de subcadenas diferentes correspondientes a cada par.

La primera línea de la entrada contiene una cadena $S (1 \leq |S| \leq 200000)$ que representa el texto del ejemplo de Fito. Le sigue un entero $N (1 \leq N \leq 200000)$ que indica la cantidad de preguntas que tiene Fito para este ejemplo. Finalmente aparecen $N$ pares de enteros $L_i$ y $C_i$ $(1 \leq L_i, C_i \leq N)$ en líneas diferentes. Cada par representa una pregunta de Fito, siendo $L_i$ la longitud y $C_i$ la cantidad de ocurrencias de las subcadenas buscadas.

Por cada pregunta de Fito, se debe imprimir una línea con la cantidad de subcadenas diferentes que tienen dicha longitud y aparecen exactamente la cantidad de veces indicada.