Un esprit maléfique s'est infiltré dans une rue de Shinjuku. Cette rue a la forme d'un segment de droite reliant une entrée située à son extrémité gauche à une sortie située à son extrémité droite, et la distance entre les deux extrémités est $10^9 + 1$.

Il y a $N$ exorcistes dans la rue. Les exorcistes sont numérotés par des entiers de $1$ à $N$ par ordre croissant de distance depuis l'entrée. L'exorciste $i$ se trouve à une distance $X_i$ ($X_i$ est un entier strictement positif) à droite de l'entrée, et tous les exorcistes occupent des positions distinctes. De plus, chaque exorciste possède l'une des deux couleurs suivantes : rouge ou bleu.

Chaque malédiction est donnée par deux entiers $a, b$. L'esprit maléfique maudit les exorcistes $a$ et $b$, en vérifiant toujours $1 \le a < b \le N$. Une zone maudite est alors créée sur le segment reliant les deux exorcistes, et cette zone maudite est l'intervalle $[X_a, X_b]$.

Une fois la zone maudite créée, les exorcistes choisissent un point de la zone maudite pour en faire la position centrale. La coordonnée de la position centrale peut être un nombre réel. Notons $c$ la position centrale. La position centrale peut coïncider avec la position d'un exorciste.

Une fois la position centrale fixée, la zone maudite est divisée en zones d'exorcisme rouges et en zones d'exorcisme bleues selon les règles suivantes.

Pour chaque $a \le i < b$, considérons l'intervalle $[X_i, X_{i+1}]$ entre deux exorcistes adjacents.

• Si $X_{i+1} \le c$, l'intervalle $[X_i, X_{i+1}]$ tout entier devient une zone d'exorcisme de la couleur de l'exorciste $i$.
• Si $c \le X_i$, l'intervalle $[X_i, X_{i+1}]$ tout entier devient une zone d'exorcisme de la couleur de l'exorciste $i+1$.
• Si $X_i < c < X_{i+1}$, l'intervalle $[X_i, c]$ devient une zone d'exorcisme de la couleur de l'exorciste $i$, et l'intervalle $[c, X_{i+1}]$ devient une zone d'exorcisme de la couleur de l'exorciste $i+1$.

Autrement dit, par rapport à la position centrale $c$, la partie située à gauche suit la couleur de l'exorciste situé à l'extrémité gauche, tandis que la partie située à droite suit la couleur de l'exorciste situé à l'extrémité droite.

Selon ces règles, chaque point de la zone maudite est couvert par une zone d'exorcisme, et des zones d'exorcisme distinctes ne peuvent se rencontrer qu'à leurs extrémités.

Lorsque la position centrale est $c$, soient $R(c)$ la longueur totale des zones d'exorcisme rouges et $B(c)$ la longueur totale des zones d'exorcisme bleues. La disharmonie de ce rituel d'exorcisme est la valeur absolue de la différence entre ces deux valeurs, c'est-à-dire $|R(c) - B(c)|$.

Afin d'augmenter les chances de réussite du rituel d'exorcisme, les exorcistes souhaitent choisir la position centrale $c$ de manière appropriée afin de minimiser la disharmonie.

Étant donné les informations sur les exorcistes et sur les malédictions lancées par l'esprit maléfique, écrivez un programme permettant de trouver la disharmonie minimale du rituel d'exorcisme pour chaque malédiction.

Entrée

La première ligne contient le nombre d'exorcistes $N$ et le nombre de malédictions $Q$, séparés par un espace. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Chacune des $N$ lignes suivantes contient la coordonnée $X_i$ et la couleur $C_i$ d'un exorciste, séparées par un espace. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R ou B)

Chacune des $Q$ lignes suivantes contient les paramètres d'une malédiction $a, b$, séparés par un espace. $a$ et $b$ sont les numéros des deux exorcistes maudits par l'esprit maléfique. ($1 \le a < b \le N$)

Sortie

Pour chaque malédiction, affichez sur une ligne séparée la disharmonie minimale correspondante. On peut prouver que la disharmonie minimale est toujours un entier.

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

0
2

Remarque

Malédiction 1 : Si l'on choisit la position centrale $c = 2.5$, les intervalles $[1, 2.5]$ et $[8, 12]$ deviennent des zones d'exorcisme rouges, tandis que les intervalles $[2.5, 6]$ et $[6, 8]$ deviennent des zones d'exorcisme bleues. Les longueurs totales des zones d'exorcisme rouges et bleues valent toutes deux $5.5$, donc la disharmonie est $0$. Choisir $c = 11.5$ comme position centrale donne également une disharmonie de $0$.

Malédiction 2 : Si l'on choisit la position centrale $c = 8$, tout l'intervalle $[6, 8]$ devient une zone d'exorcisme bleue. Comme il n'y a aucun exorciste rouge dans la zone maudite, la disharmonie ne peut pas être rendue strictement inférieure à $2$.