== include(page="template/taskheader" task_id="x") ==

In anul X, mayasii au facut rost de $2$ siruri de caractere cu litere mici ale alfabetului englez. Aceste $2$ siruri ii puteau ajuta in a ghici prost viitorul si in a afla ca pe data de $21.12.2012$ sfarsitul lumii isi va face aparitia. Ei trebuiau sa raspunda corect la urmatoarele $Q$ intrebari de forma $(x, y)$ care reprezinta: daca am elimina secventa din primul sir de la pozitia $x$ la pozitia $y$ inclusiv, si am pune in locul secventei caracterul $X$, cate secvente palindroame de lungime impara si mai mare ca $1$ exista care au centrul fixat in caracterul $X$? Deoarece la inceput au prezis bine viitorul si au aflat ca nu va veni sfarsitul lumii, ei totusi si-au dat seama ca nu folosesc la nimic cel de al doilea sir. Ca urmare au mai adaugat o propritate pe care trebuie sa o respecte sirurile palindroame cerute. La primul pas de extindere din centrul $X$, caracterul cu care se extinde sirul palindrom trebuie sa fie primul caracter din cel de al $2$-lea sir, la cel de al $2$-lea pas de extindere, caracterul trebuie sa fie cel de al $2$-lea caracter din al doilea sir, etc. Mai exact la cel de al $i$-lea pas de extindere, caracterul cu care se extinde sirul palindrom trebuie sa fie cel de al $i$-lea caracter din al doilea sir. Un pas de extindere a unui sir palindrom este atunci cand adaugi atat in stanga cat si in dreapta sirului un caracter nou (trebuie sa fie acelasi caracter pentru a se respecta proprietatea de sir palindrom). Practic un pas de extindere reprezinta marirea sirului palindrom cu $2$ caractere (unul in stanga si unul in dreapta).

In anul X, mayasii au facut rost de $2$ siruri de caractere cu litere mici ale alfabetului englez. Aceste $2$ siruri ii puteau ajuta in a ghici prost viitorul si in a afla ca pe data de $21.12.2012$ sfarsitul lumii isi va face aparitia. Ei trebuiau sa raspunda corect la urmatoarele $Q$ intrebari de forma $(x, y)$ care reprezinta: daca am elimina secventa din primul sir de la pozitia $x$ la pozitia $y$ inclusiv, si am pune in locul secventei caracterul $X$, cate secvente palindroame de lungime impara si mai mare ca $1$ exista care au centrul fixat in caracterul $X$? Deoarece la inceput au prezis bine viitorul si au aflat ca nu va veni sfarsitul lumii, ei totusi si-au dat seama ca nu folosesc la nimic cel de al doilea sir. Ca urmare au mai adaugat o propritate pe care trebuie sa o respecte sirurile palindroame cerute. La primul pas de extindere din centrul $X$, caracterul cu care se extinde sirul palindrom trebuie sa fie primul caracter din cel de al $2$-lea sir, la cel de al $2$-lea pas de extindere, caracterul trebuie sa fie cel de al $2$-lea caracter din al doilea sir, etc. Mai exact la cel de al $i$-lea pas de extindere, caracterul cu care se extinde primul sir trebuie sa fie cel de al $i$-lea caracter din al doilea sir. Un pas de extindere a unui sir palindrom este atunci cand adaugi atat in stanga cat si in dreapta sirului un caracter nou (trebuie sa fie acelasi caracter pentru a se respecta proprietatea de sir palindrom). Practic un pas de extindere reprezinta marirea sirului palindrom cu $2$ caractere (unul in stanga si unul in dreapta).

h2. Date de intrare