perioada

Perioada

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

Poveste şi cerinţă...

Mona si Lisa sunt impatimite ale jocurilor de noroc. In fiecare seara ele isi incearca sansa la o ruleta electronica speciala, care afiseaza la fiecare tura cate o litera mica a alfabetului englez. Cele doua fete au jucat noaptea trecuta $N$ ture, pariind pe exact o litera in fiecare tura. Deoarece au pierdut o suma foarte mare de bani (in dolari), fetele se gandesc ca ruleta trebuie sa fie masluita si doresc sa demonstreze stiintific acest lucru. Ele au notat pe o foaie $N$ caractere, al $i$-lea caracter reprezentand litera afisata de ruleta la cea de a $i$-a tura. Mona observa ca unele secvente de caractere aflate pe pozitii consecutive se repeta.

h2. Date de intrare

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

Fişierul de intrare $perioada.in$ contine pe prima linie numarul $N$. Cea de a doua linie contine $N$ caractere, cu semnificatia din enunt. Cea de a treia linie contine numarul $M$ de secvente care trebuiesc testate. Pe fiecare dintre urmatoarele $M$ linii se gaseste o pereche de numere naturale $x$ $y$, despartite de exact un spatiu.

h2. Date de ieşire

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

În fişierul de ieşire $perioada.out$ vor fi afisate M cifre binare, cifra de pe linia $i$ fiind $1$ doar daca cea de a $i$-a secventa din fisierul de intrare este periodica.

h2. Restricţii

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

* $1 ≤ N, M ≤ 100 000$

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

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

|10
ranananvvv
3
2 7
1 6
8 10
|1
0
1|

h3. Explicaţie

...

Secventa $ananan$ este formata prin repetarea de 3 ori a sirului $an$. Secventa $ranana$ nu este periodica.

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