excursie

Pe insula Kauai, aflată în statul Hawaii, se găsesc $N$ sate așezate în linie dreaptă, numerotate în ordine crescătoare, începând de la $1$: $1, 2, 3, \dots, N$. În dreptul fiecărui sat $i$ ($1 \le i \le N$) se află un indicator pe care poate scrie fie R, cu semnificația că din satul $i$ se poate ajunge în satul $i+1$, fie L, cu semnificația că din satul $i$ se poate ajunge în 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 în Kauai pentru $Q$ zile, tinerii John și Mary își propun să facă câte o excursie în fiecare zi. În cadrul fiecărei excursii, tinerii pornesc din sate diferite, urmărind să se întâlnească, eventual, î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$), cu semnificația: John se află inițial în satul $i$, Mary în satul $j$, iar ei încep să se deplaseze între sate, respectând sensul de deplasare de pe indicatoarele satelor vizitate.

Interesant este că cei doi au posibilitatea să înlocuiască oricât de multe indicatoare întâlnesc pe parcursul traseului și să urmeze astfel noul sens de deplasare; adică, pot înlocui un indicator R întâlnit într-unul L sau pot înlocui un indicator L întâlnit într-unul R și apoi să continue deplasarea între sate. Fiecare înlocuire a unui indicator poate fi efectuată 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ă se poată întâlni într-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 naturale $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 și precizări

• $2 \le N \le 200 \ 000$
• $1 \le Q \le 200 \ 000$
• Indicatoarele din satele $1$ și $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țială, 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 acesteia va fi egal cu $0$ dolari. De asemenea, în cadrul unei excursii, este permis ca indicația de pe un indicator întâlnit 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.

Exemplul 1

excursie.in

7
RRRLLLL
1
2 6

excursie.out

0

Explicație

Pe insulă există $N = 7$ sate, iar inițial, conform indicatoarelor din dreptul satelor:

• din satul $1$ se poate ajunge în satul $2$;
• din satul $2$ se poate ajunge în satul $3$;
• din satul $3$ se poate ajunge în satul $4$;
• din satul $4$ se poate ajunge în satul $3$;
• din satul $5$ se poate ajunge în satul $4$;
• din satul $6$ se poate ajunge în satul $5$;
• din satul $7$ se poate ajunge în satul $6$.

Va fi efectuată o singură excursie ($Q = 1$): John va începe din satul $2$, iar Mary din satul $6$. Fără a schimba niciun indicator (cost total: $0$ dolari), cei doi se pot întâlni, 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 în 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 să fie schimbate, cu costul total de $2$ dolari. De exemplu, indicatoarele din dreptul satelor $2$ și $6$ pot fi transformate din L în R. John și Mary nu se pot întâlni dacă nu schimbă cel puțin două indicatoare în cadrul acestei excursii.