En ond ånd har infiltrert en gate i Shinjuku. Denne gaten er formet som et linjestykke som forbinder en inngang i venstre ende med en utgang i høyre ende, og avstanden mellom de to endepunktene er $10^9 + 1$.

Det står $N$ trollmenn i gaten. Trollmennene har heltallsnumre fra $1$ til $N$ i rekkefølge etter hvor nær de er inngangen. Trollmann nr. $i$ befinner seg $X_i$ ($X_i$ er et positivt heltall) til høyre for inngangen, og alle trollmennene befinner seg på ulike posisjoner. I tillegg har hver trollmann én av to farger: rød eller blå.

Hver forbannelse er gitt ved to heltall $a, b$. Den onde ånden kaster en forbannelse over trollmann $a$ og $b$, og det gjelder alltid at $1 \le a < b \le N$. Da opprettes et forbannet område på linjestykket som forbinder de to trollmennene, og det forbannede området er intervallet $[X_a, X_b]$.

Når det forbannede området opprettes, velger trollmennene et punkt på det forbannede området og setter det som kjerneposisjon. Koordinaten til kjerneposisjonen kan være et reelt tall. La kjerneposisjonen være $c$. Kjerneposisjonen kan gjerne være lik posisjonen til en trollmann.

Når kjerneposisjonen er bestemt, deles det forbannede området inn i røde eksorsismeområder og blå eksorsismeområder etter følgende regler.

For hver $a \le i < b$, betrakt intervallet $[X_i, X_{i+1}]$ mellom to nabotrollmenn.

• Hvis $X_{i+1} \le c$, blir hele intervallet $[X_i, X_{i+1}]$ et eksorsismeområde med fargen til trollmann $i$.
• Hvis $c \le X_i$, blir hele intervallet $[X_i, X_{i+1}]$ et eksorsismeområde med fargen til trollmann $i+1$.
• Hvis $X_i < c < X_{i+1}$, blir intervallet $[X_i, c]$ et eksorsismeområde med fargen til trollmann $i$, og intervallet $[c, X_{i+1}]$ blir et eksorsismeområde med fargen til trollmann $i+1$.

Med andre ord, med utgangspunkt i kjerneposisjonen $c$, følger delen til venstre fargen til trollmannen i venstre endepunkt, og delen til høyre følger fargen til trollmannen i høyre endepunkt.

I henhold til reglene ovenfor dekkes hvert punkt i det forbannede området av et eksorsismeområde, og ulike eksorsismeområder kan kun møtes i endepunktene.

Når kjerneposisjonen er $c$, la $R(c)$ være den totale lengden av de røde eksorsismeområdene, og la $B(c)$ være den totale lengden av de blå eksorsismeområdene. Disharmonien til dette eksorsismeritualet er absoluttverdien av differansen mellom disse to verdiene, altså $|R(c) - B(c)|$.

For å øke sjansen for at eksorsismeritualet lykkes, ønsker trollmennene å velge kjerneposisjonen $c$ slik at disharmonien minimeres.

Gitt informasjonen om trollmennene og informasjonen om forbannelsene som den onde ånden kaster, skriv et program som finner den minimale disharmonien til eksorsismeritualet for hver forbannelse.

Inndata

På første linje gis antall trollmenn $N$ og antall forbannelser $Q$ atskilt med mellomrom. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Fra andre linje og over $N$ linjer gis trollmannens koordinat $X_i$ og farge $C_i$ atskilt med mellomrom. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R eller B)

Fra neste linje og over $Q$ linjer gis innholdet i forbannelsen $a, b$ atskilt med mellomrom. $a$ og $b$ er numrene på de to trollmennene som den onde ånden kaster forbannelse over. ($1 \le a < b \le N$)

Utdata

For hver forbannelse, skriv ut på en egen linje den minimale disharmonien for den aktuelle forbannelsen. Det kan bevises at den minimale disharmonien alltid er et heltall.

Eksempler

Inndata 1

4 2
1 R
6 B
8 B
12 R
1 4
2 3

Utdata 1

0
2

Merk

Forbannelse 1: Hvis man setter kjerneposisjonen til $c = 2.5$, blir intervallene $[1, 2.5]$ og $[8, 12]$ røde eksorsismeområder, og intervallene $[2.5, 6]$ og $[6, 8]$ blir blå eksorsismeområder. Siden den totale lengden av de røde eksorsismeområdene og den totale lengden av de blå eksorsismeområdene begge er $5.5$, er disharmonien $0$. Selv om man setter kjerneposisjonen til $c = 11.5$, blir disharmonien $0$.

Forbannelse 2: Hvis man setter kjerneposisjonen til $c = 8$, blir hele intervallet $[6, 8]$ et blått eksorsismeområde. Siden det ikke er noen rød trollmann i det forbannede området, kan ikke disharmonien gjøres mindre enn $2$.