Un espíritu maligno se ha infiltrado en una calle de Shinjuku. Esta calle tiene la forma de un segmento de recta que conecta una entrada en su extremo izquierdo con una salida en su extremo derecho, y la distancia entre ambos extremos es $10^9 + 1$.

Hay $N$ hechiceros sobre la calle. Los hechiceros están numerados con enteros entre $1$ y $N$ inclusive, en orden creciente de cercanía a la entrada. El hechicero $i$ se encuentra a una distancia $X_i$ ($X_i$ es un entero positivo) a la derecha de la entrada, y todos los hechiceros están en posiciones distintas. Además, cada hechicero tiene uno de dos colores: rojo o azul.

Cada maldición viene dada por dos enteros $a, b$. El espíritu maligno maldice a los hechiceros $a$ y $b$, cumpliéndose siempre $1 \le a < b \le N$. En ese momento se crea una región maldita sobre el segmento que une a los dos hechiceros, y la región maldita es el intervalo $[X_a, X_b]$.

Una vez creada la región maldita, los hechiceros eligen un punto de la región maldita como la posición central. La coordenada de la posición central puede ser un número real. Sea $c$ la posición central. La posición central puede coincidir con la posición donde se encuentra un hechicero.

Una vez determinada la posición central, la región maldita se divide en regiones de exorcismo rojas y regiones de exorcismo azules según las siguientes reglas.

Para cada $a \le i < b$, consideremos el intervalo $[X_i, X_{i+1}]$ entre dos hechiceros adyacentes.

• Si $X_{i+1} \le c$, todo el intervalo $[X_i, X_{i+1}]$ se convierte en una región de exorcismo con el color del hechicero $i$.
• Si $c \le X_i$, todo el intervalo $[X_i, X_{i+1}]$ se convierte en una región de exorcismo con el color del hechicero $i+1$.
• Si $X_i < c < X_{i+1}$, el intervalo $[X_i, c]$ se convierte en una región de exorcismo con el color del hechicero $i$, y el intervalo $[c, X_{i+1}]$ se convierte en una región de exorcismo con el color del hechicero $i+1$.

Es decir, tomando como referencia la posición central $c$, la parte a la izquierda sigue el color del hechicero en el extremo izquierdo, y la parte a la derecha sigue el color del hechicero en el extremo derecho.

Según las reglas anteriores, todos los puntos de la región maldita quedan cubiertos por una región de exorcismo, y regiones de exorcismo distintas solo pueden tocarse en sus extremos.

Cuando la posición central es $c$, sean $R(c)$ la longitud total de las regiones de exorcismo rojas y $B(c)$ la longitud total de las regiones de exorcismo azules. La disonancia de este ritual de exorcismo es el valor absoluto de la diferencia entre ambos valores, es decir, $|R(c) - B(c)|$.

Para aumentar la probabilidad de éxito del ritual de exorcismo, los hechiceros quieren elegir adecuadamente la posición central $c$ para minimizar la disonancia.

Dada la información de los hechiceros y de las maldiciones lanzadas por el espíritu maligno, escribe un programa que calcule la disonancia mínima del ritual de exorcismo para cada maldición.

Entrada

En la primera línea se dan el número de hechiceros $N$ y el número de maldiciones $Q$ separados por un espacio. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

En las siguientes $N$ líneas se dan la coordenada $X_i$ y el color $C_i$ de cada hechicero separados por un espacio. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R o B)

En las siguientes $Q$ líneas se da la descripción de cada maldición $a, b$ separada por un espacio. $a$ y $b$ son los números de los dos hechiceros maldecidos por el espíritu maligno. ($1 \le a < b \le N$)

Salida

Para cada maldición, imprime en una línea la disonancia mínima correspondiente a dicha maldición. Se puede demostrar que la disonancia mínima siempre es un número entero.

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

0
2

Nota

Maldición 1: Si se fija la posición central en $c = 2.5$, los intervalos $[1, 2.5]$ y $[8, 12]$ se convierten en regiones de exorcismo rojas, y los intervalos $[2.5, 6]$ y $[6, 8]$ se convierten en regiones de exorcismo azules. Como la longitud total de las regiones de exorcismo rojas y la longitud total de las regiones de exorcismo azules son ambas $5.5$, la disonancia es $0$. Si se fija la posición central en $c = 11.5$, la disonancia también resulta ser $0$.

Maldición 2: Si se fija la posición central en $c = 8$, todo el intervalo $[6, 8]$ se convierte en una región de exorcismo azul. Como no hay ningún hechicero rojo en la región maldita, la disonancia no puede hacerse menor que $2$.