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

Poveste şi cerinţă...

Se da un sir de n caractere, un modulo si o baza. Se dau q queryuri de forma mod1, mod2, l1, l2: Cate subsecvente de tip palindrom au hashul polinomial intre mod1 si mod2 si lungimea intre l1 si l2?

h2. Date de intrare
Fişierul de intrare $fft.in$ ...

baza mod
sir
q
mod1 mod2 l1 l2
..........

h2. Date de ieşire
În fişierul de ieşire $fft.out$ ...

ans1
ans2
....

h2. Restricţii
* $... ≤ ... ≤ ...$

lugime sir <= 2e5
baza si mod <= 1e18
q <= 2e5

h2. Exemplu