dorel

Î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 mică ale alfabetului englez, $S$ = $(S_1, S_2, \dots,S_N)$.

El alege la întâmplare un caracter din șir, caracter aflat pe poziția $k \ (1 \leq k \leq 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 \leq 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 \leq 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, \dots, S_{i-1}, S_{j+1}, S_{j+2}, \dots, S_N)$
• $Y = (S_i, S_{i+1}, \dots, S_j)$

Cerinţă

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 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 răspunsurile la cele $Q$ întrebări.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$
• $1 \leq Q \leq 5 \ 000$
• $N \cdot Q \leq 5 \ 000 \ 000$
• $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 $\leq 1 \ 000$

Exemplul 1

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$