Ein böser Geist ist in eine Straße in Shinjuku eingedrungen. Diese Straße hat die Form einer Strecke, die den Eingang am linken Ende mit dem Ausgang am rechten Ende verbindet, und der Abstand zwischen den beiden Endpunkten beträgt $10^9 + 1$.

Auf der Straße befinden sich $N$ Beschwörer. Die Beschwörer sind in aufsteigender Reihenfolge ihres Abstands vom Eingang mit ganzen Zahlen von $1$ bis $N$ nummeriert. Beschwörer $i$ befindet sich um $X_i$ ($X_i$ ist eine positive ganze Zahl) rechts vom Eingang, und alle Beschwörer befinden sich an paarweise verschiedenen Positionen. Außerdem besitzt jeder Beschwörer eine der beiden Farben Rot oder Blau.

Jeder Fluch wird durch zwei ganze Zahlen $a, b$ angegeben. Der böse Geist verflucht die Beschwörer $a$ und $b$, wobei stets $1 \le a < b \le N$ gilt. Dabei entsteht auf der Strecke, die die beiden Beschwörer verbindet, ein Fluchbereich, und dieser Fluchbereich ist das Intervall $[X_a, X_b]$.

Sobald der Fluchbereich entsteht, wählen die Beschwörer einen Punkt im Fluchbereich als Kernposition aus. Die Koordinate der Kernposition kann eine reelle Zahl sein. Sei $c$ die Kernposition. Die Kernposition darf auch mit der Position eines Beschwörers übereinstimmen.

Nachdem die Kernposition festgelegt wurde, wird der Fluchbereich nach den folgenden Regeln in rote Exorzismusbereiche und blaue Exorzismusbereiche unterteilt.

Für jedes $a \le i < b$ betrachten wir das Intervall $[X_i, X_{i+1}]$ zwischen zwei benachbarten Beschwörern.

• Gilt $X_{i+1} \le c$, so wird das gesamte Intervall $[X_i, X_{i+1}]$ zu einem Exorzismusbereich mit der Farbe von Beschwörer $i$.
• Gilt $c \le X_i$, so wird das gesamte Intervall $[X_i, X_{i+1}]$ zu einem Exorzismusbereich mit der Farbe von Beschwörer $i+1$.
• Gilt $X_i < c < X_{i+1}$, so wird das Intervall $[X_i, c]$ zu einem Exorzismusbereich mit der Farbe von Beschwörer $i$ und das Intervall $[c, X_{i+1}]$ zu einem Exorzismusbereich mit der Farbe von Beschwörer $i+1$.

Mit anderen Worten: Ausgehend von der Kernposition $c$ übernimmt der links liegende Teil die Farbe des Beschwörers am linken Endpunkt, während der rechts liegende Teil die Farbe des Beschwörers am rechten Endpunkt übernimmt.

Nach den obigen Regeln wird jeder Punkt des Fluchbereichs von einem Exorzismusbereich überdeckt, und verschiedene Exorzismusbereiche können sich nur an ihren Endpunkten berühren.

Wenn die Kernposition $c$ ist, sei $R(c)$ die Gesamtlänge der roten Exorzismusbereiche und $B(c)$ die Gesamtlänge der blauen Exorzismusbereiche. Die Disharmonie dieses Exorzismusrituals ist der Absolutbetrag der Differenz dieser beiden Werte, also $|R(c) - B(c)|$.

Um die Erfolgsquote des Exorzismusrituals zu erhöhen, möchten die Beschwörer die Kernposition $c$ geeignet wählen, sodass die Disharmonie minimiert wird.

Schreibe ein Programm, das anhand der Informationen über die Beschwörer und die vom bösen Geist ausgesprochenen Flüche für jeden Fluch die minimale Disharmonie des Exorzismusrituals bestimmt.

Eingabe

In der ersten Zeile werden die Anzahl der Beschwörer $N$ und die Anzahl der Flüche $Q$, getrennt durch ein Leerzeichen, gegeben. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

In den nächsten $N$ Zeilen werden jeweils die Koordinate $X_i$ und die Farbe $C_i$ eines Beschwörers, getrennt durch ein Leerzeichen, gegeben. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R oder B)

In den darauffolgenden $Q$ Zeilen werden jeweils die Angaben zu einem Fluch $a, b$, getrennt durch ein Leerzeichen, gegeben. $a$ und $b$ sind die Nummern der beiden vom bösen Geist verfluchten Beschwörer. ($1 \le a < b \le N$)

Ausgabe

Gib für jeden Fluch in einer eigenen Zeile die minimale Disharmonie für diesen Fluch aus. Es lässt sich beweisen, dass die minimale Disharmonie stets eine ganze Zahl ist.

Beispiele

Beispiel-Eingabe 1

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

Beispiel-Ausgabe 1

0
2

Hinweis

Fluch 1: Wählt man als Kernposition $c = 2.5$, so werden die Intervalle $[1, 2.5]$ und $[8, 12]$ zu roten Exorzismusbereichen und die Intervalle $[2.5, 6]$ und $[6, 8]$ zu blauen Exorzismusbereichen. Da die Gesamtlänge der roten Exorzismusbereiche und die Gesamtlänge der blauen Exorzismusbereiche jeweils $5.5$ betragen, ist die Disharmonie $0$. Auch bei Wahl der Kernposition $c = 11.5$ beträgt die Disharmonie $0$.

Fluch 2: Wählt man als Kernposition $c = 8$, so wird das gesamte Intervall $[6, 8]$ zu einem blauen Exorzismusbereich. Da sich im Fluchbereich kein roter Beschwörer befindet, kann die Disharmonie nicht kleiner als $2$ gemacht werden.