Illur andi hefur laumað sér inn í götu nokkra í Shinjuku. Þessi gata er í laginu eins og strik sem tengir inngang á vinstri enda við útgang á hægri enda, og fjarlægðin milli endapunktanna tveggja er $10^9 + 1$.

Á götunni eru $N$ særingamenn. Særingamennirnir eru númeraðir með heiltölum frá $1$ upp í $N$ í röð eftir nálægð við innganginn. Særingamaður $i$ er í fjarlægðinni $X_i$ ($X_i$ er jákvæð heiltala) hægra megin við innganginn, og allir særingamennirnir eru á ólíkum stöðum. Auk þess hefur hver særingamaður annan hvorn tveggja lita: rauðan eða bláan.

Hver bölvun er gefin með tveimur heiltölum $a, b$. Illi andinn leggur bölvun á særingamenn $a$ og $b$, og alltaf gildir $1 \le a < b \le N$. Þá myndast bölvað svæði á strikinu sem tengir særingamennina tvo, og bölvaða svæðið er bilið $[X_a, X_b]$.

Þegar bölvaða svæðið myndast velja særingamennirnir einn punkt á bölvaða svæðinu og ákveða hann sem kjarnastaðsetningu. Hnit kjarnastaðsetningarinnar getur verið rauntala. Látum kjarnastaðsetninguna vera $c$. Kjarnastaðsetningin má vera sú sama og staðsetning særingamanns.

Þegar kjarnastaðsetningin hefur verið ákveðin skiptist bölvaða svæðið í rauð særingasvæði og blá særingasvæði samkvæmt eftirfarandi reglum.

Fyrir hvert $a \le i < b$, skoðum bilið $[X_i, X_{i+1}]$ á milli tveggja aðliggjandi særingamanna.

• Ef $X_{i+1} \le c$, þá verður allt bilið $[X_i, X_{i+1}]$ að særingasvæði í lit særingamanns $i$.
• Ef $c \le X_i$, þá verður allt bilið $[X_i, X_{i+1}]$ að særingasvæði í lit særingamanns $i+1$.
• Ef $X_i < c < X_{i+1}$, þá verður bilið $[X_i, c]$ að særingasvæði í lit særingamanns $i$, og bilið $[c, X_{i+1}]$ verður að særingasvæði í lit særingamanns $i+1$.

Með öðrum orðum, miðað við kjarnastaðsetninguna $c$, fylgir hlutinn vinstra megin lit særingamannsins í vinstri endapunktinum, en hlutinn hægra megin fylgir lit særingamannsins í hægri endapunktinum.

Samkvæmt reglunum hér að ofan er sérhver punktur á bölvaða svæðinu hulinn særingasvæði, og ólík særingasvæði geta aðeins mæst í endapunktum sínum.

Þegar kjarnastaðsetningin er $c$, látum $R(c)$ vera heildarlengd rauðu særingasvæðanna og $B(c)$ vera heildarlengd bláu særingasvæðanna. Ósamræmi þessarar særingarathafnar er tölugildi mismunar þessara tveggja gilda, þ.e. $|R(c) - B(c)|$.

Til að auka líkurnar á að særingarathöfnin heppnist vilja særingamennirnir velja kjarnastaðsetninguna $c$ á viðeigandi hátt þannig að ósamræmið verði sem minnst.

Þegar upplýsingar um særingamennina og upplýsingar um bölvanirnar sem illi andinn leggur á eru gefnar, skrifaðu forrit sem finnur lágmarks ósamræmi særingarathafnarinnar fyrir hverja bölvun.

Inntak

Í fyrstu línu eru gefin fjöldi særingamanna $N$ og fjöldi bölvana $Q$ aðskilin með bili. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Frá annarri línu í $N$ línum eru gefin hnit særingamanns $X_i$ og litur $C_i$ aðskilin með bili. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R eða B)

Frá næstu línu í $Q$ línum er gefið innihald bölvunar $a, b$ aðskilið með bili. $a$ og $b$ eru númer særingamannanna tveggja sem illi andinn leggur bölvun á. ($1 \le a < b \le N$)

Úttak

Fyrir hverja bölvun skal prenta á sér línu lágmarks ósamræmi fyrir þá bölvun. Hægt er að sanna að lágmarks ósamræmið er alltaf heiltala.

Dæmi

Inntak 1

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

Úttak 1

0
2

Athugasemd

Bölvun 1: Ef kjarnastaðsetningin er ákveðin sem $c = 2.5$, verða bilin $[1, 2.5]$ og $[8, 12]$ að rauðum særingasvæðum, en bilin $[2.5, 6]$ og $[6, 8]$ verða að bláum særingasvæðum. Þar sem heildarlengd rauðu særingasvæðanna og heildarlengd bláu særingasvæðanna eru báðar $5.5$, er ósamræmið $0$. Jafnvel þótt kjarnastaðsetningin sé ákveðin sem $c = 11.5$ verður ósamræmið einnig $0$.

Bölvun 2: Ef kjarnastaðsetningin er ákveðin sem $c = 8$, verður allt bilið $[6, 8]$ að bláu særingasvæði. Þar sem enginn rauður særingamaður er á bölvaða svæðinu er ekki hægt að gera ósamræmið minna en $2$.