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

La o sear˘a dansant˘a se afl˘a N b˘aiet, i s, i fete, fiecare avˆand pe piept cˆate un num˘ar unic ˆıntre 1 s, i N. Ei se
aranjeaz˘a ˆın linie, ˆın ordinea numerelor care le sunt desemnate, la distant,˘a de 1 metru unul de cel˘alalt.
Seara se desf˘as,oar˘a pe runde de tango. ˆIn cadrul fiec˘arei runde, organizatorii aleg o subsecvent,˘a continu˘a
(dat˘a prin cap˘atul stˆang s, i cel drept) a celor N dansatori care s˘a participe la rund˘a s, i:

La o seara dansanta se afla $N$ baieti si fete, fiecare avand pe piept cate un numar unic intre $1$ si $N$. Ei se aranjeaza in linie, in ordinea numerelor care le sunt desemnate, la distanta de $1$ metru unul de celalalt. Seara se desfasoara pe runde de tango. In cadrul fiecarei runde, organizatorii aleg o subsecventa continua(data prin capatul stang si cel drept) a celor $N$ dansatori care sa participe la runda si:
 
* Daca numarul baietilor(din secventa) difera de numarul fetelor (din secventa), runda nu se danseaza;
* Daca numarul lor este identic, atunci fiecare baiat va merge sa invite cate o fata distincta la dans. Fetele vor accepta doar daca suma distantelor parcurse de baieti panal fetele alese este minima. Tangoul poate sa inceapa.
 
La sfarsitul fiecarei runde dansatorii isi reiau locurile.
 
Baietii, care spera ca aceasta seara sa fie una speciala pentru fiecare(sau cel putin pentru cat mai multi) dintre ei, va roaga ca, stiind pozitionarea initiala a dansatorilor, sa determinati pentru fiecare runda daca aceasta poate fi dansata, si, in caz afirmativ, care este suma distantelor parcuse de ei(exprimata in metri) care le va multumi pe fete.
 
Din fericire, pentru unele teste, baietii au reusit sa cada la o invoiala cu juriul si va pot spune care vor fi subsecventele pentru cateva runde in avans.

h2. Date de intrare

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

Pe prima linie a fisierului de intrare $tango2.in$ se afla numerele $N$ si $C$.
Pe a doua linie a fisierului se va afla sirul $S$, in care S[i] (indexat de la 1) = 'B' daca persoana cu numarul $i$ este baiat si 'F' altfel.
Pe a treia linie a fisierului se afla $Q$, numarul de intervale interogate.
Pe urmatoarele $Q$ linii se vor afla pe fiecare linie numerele $X$ si $Y$. Pentru $C$ = $1$ capetele intervalului sunt chiar $X$ si $Y$, iar pentru $C$ = $2$ capetele sunt $X$ *xor* $last$ si $Y$ *xor* $last$ unde $last$ este raspunsul query-ului precedent (daca acesta este primul query atunci $last$ = $0$)

h2. Date de ieşire

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

În fişierul de ieşire $tango2.out$ se vor afla pe prima linie rezultatele intrebarilor separate prin spatii.

h2. Restricţii

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

* Pentru alte 7 puncte: $1$ ≤ $N$ ≤ $2.000$, $1$ ≤ $T$ ≤ $100.000$ si $C$ = $1$
* Pentru 8 puncte: $1$ ≤ $N$ ≤ $250$, $1$ ≤ $T$ ≤ $100.000$ si $C$ = $1$
* Pentru alte 7 puncte: $1$ ≤ $N$ ≤ $100.000$, $1$ ≤ $T$ ≤ $20$ si $C$ = $1$
* Pentru alte 7 puncte: $1$ ≤ $N$ ≤ $100.000$, $1$ ≤ $T$ ≤ $100.000$ si $C$ = $2$
* Pentru alte 45 puncte: $1$ ≤ $N$ ≤ $100.000$, $1$ ≤ $T$ ≤ $100.000$ si $C$ = $1$
* Pentru alte 19 puncte: $1$ ≤ $N$ ≤ $1.000.000$, $1$ ≤ $T$ ≤ $1.000.000$ si $C$ = $1$
* Pentru alte 7 puncte: $1$ ≤ $N$ ≤ $1.000.000$, $1$ ≤ $T$ ≤ $1.000.000$ si $C$ = $2$
* _Nota: Punctajele pe subtaskuri difera (foarte putin) fata de cele din concurs._

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

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

| 16 1
BFBFBBFFFBFBBFBF
6
1 2
5 10
6 15
8 12
8 13
1 16
| 1
5
9
0
7
10

|
h3. Explicaţie

...

Acesta este un mod posibil de a realiza cea de-a treia runda de dans:
 
!problema/tango2?exp_tango.png!

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