Na pewną ulicę w Shinjuku przedostał się zły duch. Ulica ta ma kształt odcinka łączącego wejście na lewym końcu z wyjściem na prawym końcu, a odległość między oboma końcami wynosi $10^9 + 1$.

Na ulicy znajduje się $N$ zaklinaczy. Zaklinacze mają numery całkowite od $1$ do $N$ w kolejności rosnącej odległości od wejścia. Zaklinacz o numerze $i$ znajduje się w odległości $X_i$ ($X_i$ jest dodatnią liczbą całkowitą) na prawo od wejścia, a wszyscy zaklinacze znajdują się w różnych miejscach. Ponadto każdy zaklinacz ma jeden z dwóch kolorów: czerwony lub niebieski.

Każda klątwa jest opisana dwiema liczbami całkowitymi $a, b$. Zły duch rzuca klątwę na zaklinaczy o numerach $a$ i $b$, przy czym zawsze zachodzi $1 \le a < b \le N$. Wówczas na odcinku łączącym obu zaklinaczy powstaje obszar klątwy, którym jest przedział $[X_a, X_b]$.

Gdy powstaje obszar klątwy, zaklinacze wybierają jeden punkt z tego obszaru i wyznaczają go jako pozycję kluczową. Współrzędna pozycji kluczowej może być liczbą rzeczywistą. Nazwijmy pozycję kluczową $c$. Pozycja kluczowa może pokrywać się z pozycją zaklinacza.

Po wyznaczeniu pozycji kluczowej obszar klątwy zostaje podzielony na czerwone obszary egzorcyzmu i niebieskie obszary egzorcyzmu zgodnie z poniższymi zasadami.

Dla każdego $a \le i < b$ rozważmy przedział $[X_i, X_{i+1}]$ pomiędzy dwoma sąsiednimi zaklinaczami.

• Jeśli $X_{i+1} \le c$, to cały przedział $[X_i, X_{i+1}]$ staje się obszarem egzorcyzmu o kolorze zaklinacza $i$.
• Jeśli $c \le X_i$, to cały przedział $[X_i, X_{i+1}]$ staje się obszarem egzorcyzmu o kolorze zaklinacza $i+1$.
• Jeśli $X_i < c < X_{i+1}$, to przedział $[X_i, c]$ staje się obszarem egzorcyzmu o kolorze zaklinacza $i$, natomiast przedział $[c, X_{i+1}]$ staje się obszarem egzorcyzmu o kolorze zaklinacza $i+1$.

Innymi słowy, względem pozycji kluczowej $c$ część znajdująca się po lewej stronie przyjmuje kolor zaklinacza na lewym końcu, a część znajdująca się po prawej stronie przyjmuje kolor zaklinacza na prawym końcu.

Zgodnie z powyższymi zasadami każdy punkt obszaru klątwy jest pokryty przez pewien obszar egzorcyzmu, a różne obszary egzorcyzmu mogą stykać się wyłącznie na swoich końcach.

Gdy pozycją kluczową jest $c$, niech $R(c)$ oznacza łączną długość czerwonych obszarów egzorcyzmu, a $B(c)$ łączną długość niebieskich obszarów egzorcyzmu. Dysharmonią tego rytuału egzorcyzmu nazywamy wartość bezwzględną różnicy tych dwóch wartości, czyli $|R(c) - B(c)|$.

Aby zwiększyć szansę powodzenia rytuału egzorcyzmu, zaklinacze chcą odpowiednio wybrać pozycję kluczową $c$, tak aby zminimalizować dysharmonię.

Mając dane informacje o zaklinaczach oraz o klątwach rzucanych przez złego ducha, napisz program, który dla każdej klątwy wyznaczy minimalną dysharmonię rytuału egzorcyzmu.

Wejście

W pierwszym wierszu podane są liczba zaklinaczy $N$ oraz liczba klątw $Q$, oddzielone spacją. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

W kolejnych $N$ wierszach podane są współrzędna zaklinacza $X_i$ oraz jego kolor $C_i$, oddzielone spacją. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R lub B)

W następnych $Q$ wierszach podane są opisy klątw $a, b$, oddzielone spacją. $a$ i $b$ to numery dwóch zaklinaczy, na których zły duch rzuca klątwę. ($1 \le a < b \le N$)

Wyjście

Dla każdej klątwy wypisz w osobnym wierszu minimalną dysharmonię dla tej klątwy. Można udowodnić, że minimalna dysharmonia jest zawsze liczbą całkowitą.

Przykład

Wejście 1

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

Wyjście 1

0
2

Uwagi

Klątwa 1: Jeśli jako pozycję kluczową wybierzemy $c = 2.5$, przedziały $[1, 2.5]$ oraz $[8, 12]$ staną się czerwonymi obszarami egzorcyzmu, a przedziały $[2.5, 6]$ oraz $[6, 8]$ staną się niebieskimi obszarami egzorcyzmu. Łączna długość czerwonych obszarów egzorcyzmu i łączna długość niebieskich obszarów egzorcyzmu wynoszą po $5.5$, więc dysharmonia wynosi $0$. Wybranie pozycji kluczowej $c = 11.5$ również daje dysharmonię równą $0$.

Klątwa 2: Jeśli jako pozycję kluczową wybierzemy $c = 8$, cały przedział $[6, 8]$ stanie się niebieskim obszarem egzorcyzmu. Ponieważ w obszarze klątwy nie ma czerwonego zaklinacza, dysharmonii nie da się zmniejszyć poniżej $2$.