Problem
Tom Sawyer et Huckleberry Finn lisent ensemble une coupure de journal à haute voix. Mais il se trouve que Tom Sawyer a commencé à lire à partir du i-ème caractère, et Huckleberry Finn à partir du j-ème.
Combien de lettres peuvent-ils lire avant de s'apercevoir qu'ils sont partis d'endroits différents, ou jusqu'à ce qu'ils lisent tous les deux jusqu'à la fin ?
Saisie :
La première ligne contient la chaîne S (1 <= |S| <= 10
5), composée de lettres latines minuscules - une inscription tirée d'une coupure de journal.
La ligne suivante contient un nombre naturel q - le nombre de requêtes.
Les q lignes suivantes contiennent chacune deux nombres naturels i et j - les positions à partir desquelles Tom Sawyer et Huckleberry Finn commencent à lire, respectivement.
Sortie :
Imprimer q lignes, chacune devant contenir un entier - le nombre de caractères qui correspondent lors de la lecture de sous-chaînes commençant par les ième et jième caractères.
Exemples :
| Entrée |
Sortie |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |