Îl cunoașteți pe Dorel cel ”priceput” la toate. Acesta și-a propus să “strice” armonia unui șir S format din N caractere litere mici ale alfabetului englez, S=(S[1],S[2],…,S[N]).

El alege la întâmplare un caracter din șir, caracter aflat pe poziția k (1≤k≤N) și caută în stânga lui k primul caracter mai mare sau egal cu S[k], fie acesta aflat pe poziția i, S[k]≤S[i]. Dacă acesta nu există, i=1. Această alegere nu este suficientă. Dorel caută în dreapta lui k primul caracter mai mic sau egal cu S[k], fie acesta pe poziția j, S[j]≤S[k]. Dacă acesta nu există, j=N. Extrage din șirul S subșirul astfel delimitat. Ca urmare a alegerii făcute, Dorel obține două subșiruri:

• X=(S[1],S[2],…,S[i-1],S[j+1],S[j+2],…,S[N])
• Y=(S[i],S[i+1],…,S[j])

Cerința

Cunoscând șirul S, ajutați-l pe Dorel să răspundă la Q întrebări de forma:

• Pentru o poziție k din șirul S să se determine lungimea maximă a unei subsecvențe palindromice comune șirurilor X și Y.

Date de intrare

Fișierul de intrare dorel.in conține pe prima linie pe prima linie un șir de caractere. Pe cea de-a doua linie o valoare naturală nenulă Q. Pe următoarea linie cele Q întrebări în formatul precizat în enunț.

Date de ieșire

Fișierul de ieșire dorel.out va conține pe prima linie răspunsurile la cele Q întrebări, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ N ≤ 10000
• 1 ≤ Q ≤ 5000
• N * Q ≤ 5000000
• X și Y sunt șiruri nevide
• prin subsecvență palindromică a unui șir înțelegem o succesiune de caractere aflate pe poziții consecutive în șir care este palindrom (subsecvența parcursă de la stânga la dreapta este identică cu secvența parcursă de la dreapta la stânga).
• lungimea maximă a unei subsecvențe palindromice comune ≤ 1000

Exemplu:

dorel.in

xexxxdexxexaegf
4
6 8 15 3

dorel.out

4 2 0 3

Explicație

Răspunsul la cele 4 întrebări

X=”xexxegf”, Y=”xdexxexa”.
Subsecvența palindromică comună =”exxe” având lungimea =4

X=”xexxexaegf”, Y=”xdexx”
Subsecvența palindromică comună =”xx” având lungimea =2

X=”xexxxdexxexae”, Y=”gf”
Subsecvența palindromică comună =”” având lungimea =0

X=”xdexxexaegf”, Y=”xexx”
Subsecvența palindromică comună =”xex” având lungimea =3