Problem
Tom Sawyer e Huckleberry Finn leram juntos um recorte de jornal em voz alta. Mas aconteceu que Tom Sawyer começou a ler do i-ésimo caractere, e Huckleberry Finn do j-ésimo.
Quantas letras eles podem ler antes de descobrirem que começaram em lugares diferentes, ou até que ambos leiam até o fim?
Entrada:
A primeira linha contém a string S (1 <= |S| <= 10
5), consistindo de letras latinas minúsculas - uma inscrição de um recorte de jornal.
A próxima linha contém um número natural q - o número de solicitações.
As próximas q linhas contêm dois números naturais i e j cada - as posições a partir das quais Tom Sawyer e Huckleberry Finn começam a ler, respectivamente.
Saída:
Imprima q linhas, cada uma das quais deve conter um número inteiro - o número de caracteres que correspondem ao ler substrings começando com os caracteres i-ésimo e j-ésimo.
Exemplos:
| Entrada |
Saída |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |