excursie

Pe insula Kauai, aflată în satul Hawaii, se găsesc $N$ sate așezate in linei dreaptă, numerotate în ordine crescătoare, începând de la $1$ : $1, 2, 3, \cdots , N$. În dreptul fiecărui sat $i$ ( $1 \le i \le N$ ) se află un indicator pe care poate fie scris fie R, cu semntificația că din satul $i$ se poate ajunge in satul $(i+1)$, Fie L, cu semnificația că din satul i se poate ajunge in satul $(i-1)$. Se știe faptul că pe indicatorul satului 1 este scris R, iar pe cel al satului $N$ este scris L.

Ajunși in Kauai pentru $Q$ zile, tinerii John și Mary își propun să facă câte o excursie în fiecare zi. În cadrul ficărie excursii, tinerii pornesc din sate diferite, urmărind să se întâlnească, eventul, într-unul dintre cele $N$ sate. Fiecare excursie va fi reprezentată sub forma $(i,j)$ (unde $1 \le i, j \le N$ și $i \neq j$)

Interesant este că cei doi au posibilitatea să înlocuiască oricât de multe indicatoare întlânesc pe parcursul traseului și să urmeze astfel noul sens de desplasare; adică, pot înlocui un indicator R întalnit într-unul L sau pot înlocui un indicator L întâlnit într-unul R și apoi sa continue deplasarea între sate. Fiecare înlocuire a unui indicator poate fi efecuată dacă se achită o taxă în valoare de 1 dolar. Pe durata excursiei, din cauza căldurii, tinerii pot alege și să staționeze în satele în care se găsesc la un moment dat (inclusiv în satele din care pornesc), adică nu este nevoie ca cei doi să se deplaseze simultan între sate pe durata întregului traseu. Important este ca cei doi, într-un final, să se întâlnesc într-un sat.

Cerință

Pentru fiecare dintre cele $Q$ excursii, se cere să se determine costul total minim, exprimat în dolari, care va fi plătit pentru ca cei doi tineri să poată întalni întru-unul dintre cele $N$ sate, eventual după modificarea a 0 sau mai multe indicatoare din satele vizitate.

Date de intrare

Pe prima linie a fișierului de intrare excursie.in se află numărul natural nenul $N$, cu semnificația de mai sus. Pe următoarea linie se află, fără niciun spațiu între ele, $N$ caractere ce pot fi fie 'R', fie 'L', al $i$-lea caracter reprezentând ce este scris inițial pe indicatorul din dreptul satului $i$. Pe cea de a treia linie se află numărul natural nenul $Q$, reprezenând numărul de excursii. Pe următoarele $Q$ linii se află, separate prin câte un spațiu, câte două numere natulare $i$ și $j$, descriind, în ordine, excursiile tinerilor, adică satele din care pornesc cei doi în fiecare dintre cele $Q$ zile.

Date de ieșire

Fișierul de ieșire excursie.out va conține $Q$ linii, pe cea de a $i$-a linie aflându-se costul total minim necesar efectuării excursiei din ziua $i$, pentru fiecare $i$: $1 \le i \le Q$

Restricții

• $2 \le N \le 200 \ 000$ și $1 \le Q \le 200 \ 000$.
• Indicatoarele din satele 1 si $N$ nu pot fi modificate.
• Chiar dacă pentru efectuarea unei excursii dintre cele $Q$ se pot modifica indicatoarele anumitor sate, în timpul nopții, înainte de începerea următoarei excursii, acestea vor reveni la starea inițtială, așa cum au fost descrise în fișierul de intrare.
• Dacă pentru efectuarea unei excursii nu este necesar să fie schimbat niciun indicator, atunci costul (total) aferent acestia va fi egal cu 0 dolari. De asemenea, în cadrul unei excursii, este permis ca indicația de pe un indicator intânlnit pe parcursul traseului să fie schimbată de mai multe ori.
• Este posibil ca pentru efectuarea unei excursii să existe mai multe modalități de a modifica indicatoarele astfel încât costul total să fie minim

Subtask 1 (9 puncte)

• $|i-j| = 1$, pentru fiecare dintre cele $Q$ excursii

Subtask 2 (7 puncte)

• Toate indicatoarele arată inițial R, cu excepția celui din dreptul satului $N$

Subtask 3 (6 puncte)

• Toate indicatoarele arată inițial L, cu excepția celui din dreptul satului 1

Subtask 4 (11 puncte)

• $N \le 200$ și $Q \le 300$

Subtask 5 (29 puncte)

• $N,Q \le 3 \ 000$

Subtask 6 (22 puncte)

• $N,Q \le 70 \ 000$

Subtask 7 (16 puncte)

• Nu există alte restricții suplimentare

Exemplul 1

excursie.in

7
RRRLLLL
1
2 6

excursie.out

0

Explicație

• Pe insulă exista $N = 7$ sate, iar ințial, conform indicatoarelor din dreptul satelor:
  • din satul 1 se poate ajunge in satul 2;
  • din satul 2 se poate ajunge in satul 3;
  • din satul 3 se poate ajunge in satul 4;
  • din satul 4 se poate ajunge in satul 3;
  • din satul 5 se poate ajunge in satul 4;
  • din satul 6 se poate ajunge in satul 5;
  • din satul 7 se poate ajunge in satul 6;
• Va fi efectuată o singură excursie ($Q = 1$) : John va începe din satul 2, iar Mary din satul 6. Fără a schibma niciun indicator (cost total: 0 dolari), cei doi se pot întalni, de exemplu, în satul 3, respectând indicațiile de pe indicatoarele întâlnite. Astfel, John se va deplasa din satul 2 în satul 3. De asemenea, Mary se va deplasa, pornind din satul 6, în satul 5, apoi în satul 4, iar in cele din urmă în satul 3, unde se va întalni cu John

Exemplul 2

excursie.in

5
RRLRL
3
1 3
4 1
2 5

excursie.out

0
1
1

Explicație

• Pentru cea de a doua excursie (4, 1), este necesar ca cel puțin un indicator să fie schimbat, cu costul de 1 dolar. De exemplu, indicatorul din dreptul satului 3 poate fi transformat din L în R

Exemplul 3

excursie.in

8
RLRRRLRL
4
2 4
1 6
2 8
6 2

excursie.out

1
1
2
1

Explicație

• Pentru cea de a treia excursie (2, 8), este nevoie de cel puțin două indicatoare sa fie schimbate, cu costul total de 2 dolari. De exemplu, indicatoarele din dreptul satelor 2 si 6 pot fi transformate din L în R. John si Mary nu se pot întalni dacă nu schimbă cel puțin două indicatoare în cadrul acestei excursii