En ond ande har infiltrerat en gata i Shinjuku. Gatan är formad som ett linjesegment som förbinder en ingång vid dess vänstra ändpunkt med en utgång vid dess högra ändpunkt, och avståndet mellan de två ändpunkterna är $10^9 + 1$.

Det finns $N$ besvärjare på gatan. Besvärjarna är numrerade med heltal från $1$ till $N$ i stigande ordning efter avstånd från ingången. Besvärjare $i$ befinner sig $X_i$ ($X_i$ är ett positivt heltal) till höger om ingången, och alla besvärjare befinner sig på olika positioner. Dessutom har varje besvärjare en av två färger: röd eller blå.

Varje förbannelse ges av två heltal $a, b$. Den onda anden kastar en förbannelse över besvärjare $a$ och $b$, där $1 \le a < b \le N$ alltid gäller. Då skapas ett förbannat område på linjesegmentet som förbinder de två besvärjarna, och det förbannade området är intervallet $[X_a, X_b]$.

När det förbannade området skapas väljer besvärjarna en punkt på det förbannade området och bestämmer den som kärnposition. Koordinaten för kärnpositionen kan vara ett reellt tal. Låt kärnpositionen vara $c$. Kärnpositionen får sammanfalla med en besvärjares position.

När kärnpositionen har bestämts delas det förbannade området upp i röda exorcismområden och blå exorcismområden enligt följande regler.

För varje $a \le i < b$, betrakta intervallet $[X_i, X_{i+1}]$ mellan två intilliggande besvärjare.

• Om $X_{i+1} \le c$, blir hela intervallet $[X_i, X_{i+1}]$ ett exorcismområde med samma färg som besvärjare $i$.
• Om $c \le X_i$, blir hela intervallet $[X_i, X_{i+1}]$ ett exorcismområde med samma färg som besvärjare $i+1$.
• Om $X_i < c < X_{i+1}$, blir intervallet $[X_i, c]$ ett exorcismområde med samma färg som besvärjare $i$, och intervallet $[c, X_{i+1}]$ blir ett exorcismområde med samma färg som besvärjare $i+1$.

Med andra ord, utgående från kärnpositionen $c$ följer delen till vänster färgen hos besvärjaren vid den vänstra ändpunkten, och delen till höger följer färgen hos besvärjaren vid den högra ändpunkten.

Enligt reglerna ovan täcks varje punkt i det förbannade området av ett exorcismområde, och olika exorcismområden kan endast mötas i sina ändpunkter.

När kärnpositionen är $c$, låt $R(c)$ vara den totala längden av de röda exorcismområdena och $B(c)$ vara den totala längden av de blå exorcismområdena. Disharmonin hos denna exorcismritual är absolutbeloppet av skillnaden mellan dessa två värden, det vill säga $|R(c) - B(c)|$.

För att öka ritualens chans att lyckas vill besvärjarna välja kärnpositionen $c$ lämpligt så att disharmonin minimeras.

Givet informationen om besvärjarna och informationen om förbannelserna som den onda anden kastar, skriv ett program som finner den minimala disharmonin för exorcismritualen för varje förbannelse.

Indata

På första raden ges antalet besvärjare $N$ och antalet förbannelser $Q$, separerade med ett mellanslag. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Från den andra raden ges på $N$ rader besvärjarens koordinat $X_i$ och färg $C_i$, separerade med ett mellanslag. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R eller B)

Från nästa rad ges på $Q$ rader förbannelsens innehåll $a, b$, separerade med ett mellanslag. $a$ och $b$ är numren på de två besvärjare som den onda anden förhäxar. ($1 \le a < b \le N$)

Utdata

För varje förbannelse, skriv ut på en egen rad den minimala disharmonin för den förbannelsen. Det kan bevisas att den minimala disharmonin alltid är ett heltal.

Exempel

Indata 1

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

Utdata 1

0
2

Anmärkning

Förbannelse 1: Om kärnpositionen väljs till $c = 2.5$, blir intervallen $[1, 2.5]$ och $[8, 12]$ röda exorcismområden, och intervallen $[2.5, 6]$ och $[6, 8]$ blir blå exorcismområden. Eftersom den totala längden av de röda exorcismområdena och den totala längden av de blå exorcismområdena båda är $5.5$, är disharmonin $0$. Även om man väljer kärnpositionen till $c = 11.5$ blir disharmonin $0$.

Förbannelse 2: Om kärnpositionen väljs till $c = 8$, blir hela intervallet $[6, 8]$ ett blått exorcismområde. Eftersom det inte finns någon röd besvärjare i det förbannade området kan disharmonin inte göras mindre än $2$.