Problem
Tom Sawyer y Huckleberry Finn leen juntos en voz alta un recorte de periódico. Pero dio la casualidad de que Tom Sawyer empezó a leer del i-ésimo carácter, y Huckleberry Finn del j-ésimo.
¿Cuántas letras pueden leer antes de darse cuenta de que comenzaron en diferentes lugares, o hasta que ambos lean hasta el final?
Entrada:
La primera línea contiene la cadena S (1 <= |S| <= 10
5), que consiste en letras latinas minúsculas, una inscripción de un recorte de periódico.
La siguiente línea contiene un número natural q - el número de solicitudes.
Las siguientes líneas q contienen dos números naturales i y j cada uno, las posiciones desde las que Tom Sawyer y Huckleberry Finn comienzan a leer, respectivamente.
Salida:
Imprima q líneas, cada una de las cuales debe contener un número entero: la cantidad de caracteres que coinciden al leer subcadenas que comienzan con los caracteres i-th y j-th.
Ejemplos:
| Entrada |
Salida |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |