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

Poveste şi cerinţă...

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).

h2. Date de intrare

Fişierul de intrare $x.in$ ...

Fişierul de intrare $x.in$ va contine pe prima linie $3$ numere naturale $N$, $M$, $Q$. $N$ este lungimea primului sir, $M$ este lungimea celui de al doilea sir iar $Q$ este numarul de intrebari. A doua linie contine un sir de $N$ caractere ce reprezinta primul sir. A treia linie contine un sir de $M$ caractere ce reprezinta cel de al doilea sir. Pe urmatoarele $Q$ linii sunt cele $Q$ intrebari de forma $(x, y)$.

h2. Date de ieşire

În fişierul de ieşire $x.out$ ...

Fişierul de ieşire $x.out$ va contine $Q$ linii. Pe linia $i$ trebuie sa afisati raspunsul la intrebarea $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 1.000.000$
* $1 ≤ Q ≤ 500.000$

h2. Exemplu

h3. Explicaţie

...

Primul pas de extindere va fi facut de caracterul 'a' iar cel de al doilea va fi facut de catre caracterul 'b'.

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

9281