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

Poveste şi cerinţă...

SMB a studiat la biologie structura secventelor ADN. El primeste o secventa ADN de lungime $N$, secventa ce contine doar caracterele $A$, $C$, $G$ sau $T$. El primeste apoi $M$ intrebari de genul: care este numarul minim de caractere din secventa care trebuie modificate astfel incat subsecventa situata intre pozitiile $x$ si $y$ in sir sa fie periodica? De exemplu, subsecventa $ACTACT$ este periodica de lungime $3$, iar subsecventa $ACTACTA$ nu este periodica.

h2. Date de intrare

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

Fişierul de intrare $perb.in$ va contine pe prima linie doua numere naturale, $N$ si $M$, avand semnificatia din enunt. Pe urmatoarea linie urmeaza sirul ADN. Pe urmatoarele $M$ linii se afla cate doua numere naturale $x$ si $y$ avand semnificatia din enunt.

h2. Date de ieşire

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

În fişierul de ieşire $perb.out$ se vor afla $M$ linii, pe fiecare linie aflandu-se raspunsul la intrebarile din fisierul de intrare.

h2. Restricţii

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

* $1 ≤ N ≤ 600$
* $1 ≤ M ≤ 500 000$

h2. Exemplu