intervale

Cosmin și Lensu se plimbau pe plajele periculoase din Egipt, când au zărit un rechin care „căra” după el un șir s de caractere. Din moment ce Harry Potter i-a învățat pe cei doi cum să comunice cu animalele, Cosmin și Lensu au îmblânzit rechinul, făcându-l să le dea șirul de caractere. Aceștia doresc să îl păstreze, dar rechinul le-a spus că îl va lua înapoi dacă aceștia nu vor răspunde la mai multe întrebări adresate de el.

Cerința

Se dă un șir s de caractere și $T$ interogări de forma $stânga, \ dreapta$. Rechinul vă întreabă dacă literele din secvența $[stânga, \ dreapta]$ a șirului s se pot rearanja astfel încât să formeze un cuvânt palindromic.

Date de intrare

Pe prima linie se va regăsi numărul natural $T$, iar pe a doua linie se va afla șirul de caractere s, reprezentând numărul de întrebări pe care le pune rechinul. Pe următoarele $T$ linii se vor afla două numere, $stânga$ și $dreapta$, reprezentând începutul, respectiv sfârșitul secvenței pe care se face interogarea. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Se vor afișa $T$ linii, pe fiecare linie $i \ (1 ≤ i ≤ T)$ identificându-se un singur cuvânt, $„DA”$ sau $„NU”$, răspunsul la întrebarea $i$ a rechinului.

Restricții și precizări

• șirul s este format doar din litere mici ale alfabetului englez;
• $2 \leq |S| \leq 5 \ 000 \ 000$, unde $|S|$ reprezintă lungimea șirului dat;
• $1 \leq T \leq 1 \ 000 \ 000$;
• $1 \leq stânga \leq dreapta \leq |S|$;

  #	Punctaj	Restricții
  1	31	$T \leq 50$ și $\vert S \vert \leq 10^5$
  2	47	$T \leq 100 \ 000$ și $\vert S \vert \leq 10^5$
  3	22	Fără alte restricții suplimentare

Observație

Datorită datelor de intrare foarte mari, se vor folosi instrucțiunile următoare la începutul programului:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplu

stdin

2
zabac
2 4
3 5

stdout

DA
NU

Explicație

Litere din secvența [2, 4] formează deja, în ordinea din șirul dat, un cuvânt palindromic, astfel că răspunsul primei întrebări este $„DA”$.
Litere din secvența [3, 5], mai exact a, b și c, nu pot fi rearanjate astfel încât să formeze un cuvânt palindromic. Deci, răspunusul întrebării cu numărul 2 este $„NU”$.