Tango

La o seară dansantă se află N băieți și fete, fiecare având pe piept câte un număr unic între 1 și N. Ei se aranjează în linie, în ordinea numerelor care le sunt desemnate, la distanță de 1 metru unul de celălalt. Seara se desfășoară pe runde de tango. În cadrul fiecărei runde, organizatorii aleg o subsecvență continuă (dată prin capătul stâng și cel drept) a celor N dansatori care să participe la rundă și:

• Dacă numărul băieților (din secvență) diferă de numărul fetelor (din secvență), runda nu se dansează;
• Dacă numărul lor este identic, atunci fiecare băiat va merge să invite câte o fată distinctă la dans. Fetele vor accepta doar dacă suma distanțelor parcurse de băieți până la fetele alese este minimă. Tangoul poate să înceapă.

La sfârșitul fiecărei runde, dansatorii își reiau locurile.

Băieții, care speră ca această seară să fie una specială pentru fiecare (sau cel puțin pentru cât mai mulți) dintre ei, vă roagă ca, știind poziționarea iniț ială a dansatorilor, să determinați pentru fiecare rundă dacă aceasta poate fi dansată, și, în caz afirmativ, care este suma distanțelor parcurse de ei (exprimată în metri) care le va mulțumi pe fete.

Din fericire, pentru unele teste, băieții au reușit să cadă la o învoială cu juriul și vă pot spune care vor fi subsecvențele pentru câteva runde în avans.

Detalii de implementare

Veți implementa două funcții cu următoarele antete:

void init(std::string s)
std::vector<long long> dance(std::vector<int> l, std::vector<int> r)

Șirul s din cadrul procedurii init este format din N caractere din mulțimea {B, F}. Dacă $s_k = B$, se consideră că dansatorul cu numărul k + 1 este băiat, iar dacă $s_k = F$, dansatoarea cu numărul k + 1 este fată (0 ≤ k < N). Vectorii l și r din cadrul funcției dance au aceeași dimensiune (o vom nota Q) și reprezintă capetele subsecvenței fiecărei runde de dans date de către juriu în avans la momentul respectiv. Mai exact, runda i + 1 (0 ≤ i < Q) de dans va fi alcătuită de către concurenții $[l_i, l_{i + 1}, ..., r_i]$.

Atenție! Pentru fiecare test, funcția init va fi apelată o singură dată, la începutul programului, apoi funcția dance va fi apelată cel puțin o dată. Pentru fiecare apel al funcției se garantează că lungimile vectorilor l și r sunt pozitive și egale $(|l| = |r| = Q)$ și că $1 ≤ l_i ≤ r_i ≤ N$ pentru orice 0 ≤ i < Q.

Funcția dance trebuie să returneze un vector de lungime Q de numere naturale cuprinse între $0$ și $10^{18}$, reprezentând răspunsurile pentru fiecare din runde. În vectorul respectiv pe poziția i se va afla răspunsul (exprimat în metri) pentru runda de dans caracterizată prin $l_i$ și $r_i$ (0 ≤ i < Q). În cazul în care numărul băieților din subsecvență este diferit de cel al fetelor, se consideră că răspunsul este 0 (întrucât băieții se prind repede de acest fapt și nu se mișcă deloc).

Punctare

T reprezintă numărul total de runde din cadrul unui test (formal, notăm $T = \sum Q$, unde se va suma după toate apelurile funcției dance).

Subtaks 1 (5 puncte)

• 1 ≤ N ≤ 250
• 1 ≤ T ≤ 100 000
• Funcția dance va fi apelată exact o dată.

Subtaks 2 (13 puncte)

• 1 ≤ N ≤ 2 000
• 1 ≤ T ≤ 100 000
• Funcția dance va fi apelată exact o dată.

Subtaks 3 (5 puncte)

• 1 ≤ N ≤ 100 000
• 1 ≤ T ≤ 20
• Funcția dance va fi apelată exact o dată.

Subtaks 4 (46 de puncte)

• 1 ≤ N ≤ 100 000
• 1 ≤ T ≤ 100 000
• Funcția dance va fi apelată exact o dată.

Subtaks 5 (7 puncte)

• 1 ≤ N ≤ 100 000
• 1 ≤ T ≤ 100 000
• Funcția dance va fi apelată de cel mult T ori.

Subtaks 6 (19 puncte)

• 1 ≤ N ≤ 1 000 000
• 1 ≤ T ≤ 1 000 000
• Funcția dance va fi apelată exact o dată.

Subtaks 7 (5 puncte)

• 1 ≤ N ≤ 1 000 000
• 1 ≤ T ≤ 1 000 000
• Funcția dance va fi apelată de cel mult T ori.

Model de grader

Observație: Modelul de grader va apela o singură dată funcția dance.
Graderul va citi de la consolă datele de intrare în următorul format:

• linia 1: s (|s| = N), reprezentând configurația inițială a dansatorilor
• linia 2: Q, reprezentând numărul de runde de dans
• linia 3 + i (0 ≤ i < Q): $l_i \ r_i$ (separate prin spațiu), reprezentând runda i + 1
  Graderul va afișa la consolă răspunsul vostru în următorul format:
• linia 1 + i: (0 ≤ i < Q): răspunsul pentru runda i + 1

Exemplu

stdin

BFBFBBFFFBFBBFBF
6
1 2
5 10
6 15
8 12
8 13
1 16

stdout

1
5
9
0
7
10

Explicație

Acesta este un mod posibil de a realiza cea de-a treia rundă de dans: