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

Dupa cum bine stiti, polinoamele sunt o parte cruciala a matematicii fara de care dezvoltarea, atat pe plan tehnologic, cat si pe plan social (daca nu am vorbi despre polinoame, atunci despre ce am mai vorbi?!), nu ar fi fost posibile. Dar mai intai, ce este cu adevarat un polinom? Un matematician adevarat o sa va spuna ca un polinom este o expresie care are in componenta sa o variabila, de regula notata cu $x$, un set de constante, numite coeficienti, si care admite drept operatii numai adunarea, scaderea, inmultirea si ridicarea la putere constanta, numar natural. Mai mult, v-ar putea spune ca, in general, un polinom definit pe o multime $M$ are urmatoarea forma: $P(x) = a[~0~] + a[~1~] * x + a[~2~] * x^2^ + ... + a[~n~] * x^n^$, unde $n$ este un numar natural, iar $a[~0~], a[~1~], a[~2~], ..., a[~n~]$ sunt constante si fac parte din $M$. Asta este complet neadevarat! Un polinom este, de fapt, o unealta diabolica cu ajutorul careia comisia poate tortura concurentii fara sa se chinuie prea tare. Daca va intrebati cum, este foarte simplu. Se iau doua polinoame (daca se poate sa aiba coeficientii luati de pe O.E.I.S., este cu atat mai bine) si se cere sa se inmulteasca intre ele in complexitate $O(n * log[~2~]n)$. Credeti ca asta nu este posibil? Ati fi surprinsi! Din fericire pentru voi, noi consideram ca ar fi prea demodat sa cerem aplicarea algoritmului Fast Fourier Transformation (a se vedea "Strada Cramei":https://infoarena.ro/problema/stradacramei). Asa ca, ne-am gandit sa mai aprofundam putin utilitatea acestori minuni revolutionare si am aflat ca le poti folosi pentru a transforma un sir de caractere, intr-un numar, numit cheie. Tot ce trebuie sa faci este sa iti alegi un numar natural $b$, un numar natural $m$, sa iti consideri drept $a[~i~]$ codul ASCII al caracterului aflat pe pozitia $i$ in sirul de caractere (indexat de la $0$) si sa calculezi $P(b) MOD m$. Pentru a nu va chinui prea tare, comisia va ofera atat sirul de caractere, cat si numerele $b$ si $m$, dar va cere in schimb sa raspundeti la $q$ intrebari de forma: Cate subsecvente de tip palindrom au lungimea cuprinsa intre $l[~1~]$ si $l[~2~]$ si cheia cuprinsa intre $m[~1~]$ si $m[~2~]$?

Dupa cum bine stiti, polinoamele sunt o parte cruciala a matematicii fara de care dezvoltarea, atat pe plan tehnologic, cat si pe plan social (daca nu am vorbi despre polinoame, atunci despre ce am mai vorbi?!), nu ar fi fost posibile. Dar mai intai, ce este cu adevarat un polinom? Un matematician adevarat o sa va spuna ca un polinom este o expresie care are in componenta sa o variabila, de regula notata cu $x$, un set de constante, numite coeficienti, si care admite drept operatii numai adunarea, scaderea, inmultirea si ridicarea la putere constanta, numar natural. Mai mult, v-ar putea spune ca, in general, un polinom definit pe o multime $M$ are urmatoarea forma: $P(x) = a[~0~] + a[~1~] * x + a[~2~] * x^2^ + ... + a[~n~] * x^n^$, unde $n$ este un numar natural, iar $a[~0~], a[~1~], a[~2~], ..., a[~n~]$ sunt constante si fac parte din $M$. Asta este complet neadevarat! Un polinom este, de fapt, o unealta diabolica cu ajutorul careia comisia poate tortura concurentii fara sa se chinuie prea tare. Daca va intrebati cum, este foarte simplu. Se iau doua polinoame (daca se poate sa aiba coeficientii luati de pe O.E.I.S., este cu atat mai bine) si se cere sa se inmulteasca intre ele in complexitate $O(n * log[~2~]n)$. Credeti ca asta nu este posibil? Ati fi surprinsi! Din fericire pentru voi, noi consideram ca ar fi prea demodat sa cerem aplicarea algoritmului Fast Fourier Transformation (a se vedea "Strada Cramei":https://infoarena.ro/problema/stradacramei). Asa ca, ne-am gandit sa mai aprofundam putin utilitatea acestori minuni revolutionare si am aflat ca le poti folosi pentru a transforma un sir de caractere, intr-un numar natural, numit cheie. Tot ce trebuie sa faci este sa iti alegi un numar natural $b$, un numar natural nenul $m$, sa iti consideri drept $a[~i~]$ codul ASCII al caracterului aflat pe pozitia $i$ in sirul de caractere (indexat de la $0$) si sa calculezi $P(b) MOD m$. Pentru a nu va chinui prea tare, comisia va ofera atat sirul de caractere, cat si numerele $b$ si $m$, dar va cere in schimb sa raspundeti la $q$ intrebari de forma: Cate subsecvente de tip palindrom au lungimea cuprinsa intre $l[~1~]$ si $l[~2~]$ si cheia cuprinsa intre $m[~1~]$ si $m[~2~]$?

h2. Date de intrare

Fişierul de intrare $fft.in$ ...
baza mod
sir
q
mod1 mod2 l1 l2
..........

Fişierul de intrare $fft.in$ contine pe prima linie numerele $b$ si $m$, avand semnificatia din enunt. A doua linie contine un sir de caractere, de lungime $n$. A treia linie contine numarul $q$, reprezentand numarul de intrebari la care comisia va cere sa raspundeti. Fiecare dintre urmatoarele $q$ linii contine un set de numere $m[~1~]$ $m[~2~]$ $l[~1~]$ $l[~2~]$, reprezentand o intrebare.

h2. Date de ieşire

În fişierul de ieşire $fft.out$ ...
ans1
ans2
....

În fişierul de ieşire $fft.out$ se vor afisa raspunsurile pentru fiecare intrebare, pe linii separate, in ordinea in care acestea au fost citite.

h2. Restricţii

* $... ≤ ... ≤ ...$
lugime sir <= 2e5
baza si mod <= 1e18
q <= 2e5

* $1 ≤ n ≤ 200.000$
* $1 ≤ q ≤ 200.000$
* $0 ≤ b ≤ 10^18^$
* $1 ≤ m ≤ 10^18^$
* $0 ≤ $m[~1~]$ ≤ 10^18^$
* $0 ≤ $m[~2~]$ ≤ 10^18^$
* $0 ≤ $l[~1~]$ ≤ n$
* $0 ≤ $l[~2~]$ ≤ n$

h2. Exemplu
table(example). |_. fft.in |_. fft.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| $3 1000000$
  $aaba$
  $2$
  $17 199 1 1$
  $99 5000 1 3$
| $4$
  $2$

|
h3. Explicaţie

...

Pentru prima intrebare subsecventele sunt: [0, 0], [1, 1], [2, 2], [3, 3].
Pentru a doua intrebare subsecventele sunt: [0, 1], [1, 3].

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