Uno spirito maligno si è infiltrato in una strada di Shinjuku. Questa strada ha la forma di un segmento che collega un ingresso all'estremità sinistra con un'uscita all'estremità destra, e la distanza tra i due estremi è $10^9 + 1$.

Ci sono $N$ stregoni lungo la strada. Gli stregoni sono numerati con interi da $1$ a $N$ in ordine crescente di distanza dall'ingresso. Lo stregone $i$ si trova a una distanza $X_i$ ($X_i$ è un intero positivo) a destra dell'ingresso, e tutti gli stregoni si trovano in posizioni distinte. Inoltre, ciascuno stregone possiede uno tra due colori: rosso oppure blu.

Ogni maledizione è data da due interi $a, b$. Lo spirito maligno lancia una maledizione sugli stregoni $a$ e $b$, soddisfacendo sempre $1 \le a < b \le N$. In tal caso viene creata una regione maledetta sul segmento che collega i due stregoni, e la regione maledetta è l'intervallo $[X_a, X_b]$.

Quando viene creata la regione maledetta, gli stregoni scelgono un punto nella regione maledetta e lo fissano come posizione centrale. La coordinata della posizione centrale può essere un numero reale. Sia $c$ la posizione centrale. La posizione centrale può coincidere con la posizione di uno stregone.

Una volta fissata la posizione centrale, la regione maledetta viene suddivisa in regioni di esorcismo rosse e regioni di esorcismo blu secondo le regole seguenti.

Per ogni $a \le i < b$, consideriamo l'intervallo $[X_i, X_{i+1}]$ tra due stregoni adiacenti.

• Se $X_{i+1} \le c$, l'intero intervallo $[X_i, X_{i+1}]$ diventa una regione di esorcismo del colore dello stregone $i$.
• Se $c \le X_i$, l'intero intervallo $[X_i, X_{i+1}]$ diventa una regione di esorcismo del colore dello stregone $i+1$.
• Se $X_i < c < X_{i+1}$, l'intervallo $[X_i, c]$ diventa una regione di esorcismo del colore dello stregone $i$, mentre l'intervallo $[c, X_{i+1}]$ diventa una regione di esorcismo del colore dello stregone $i+1$.

In altre parole, rispetto alla posizione centrale $c$, la parte a sinistra segue il colore dello stregone nell'estremo sinistro, mentre la parte a destra segue il colore dello stregone nell'estremo destro.

In base alle regole precedenti, ogni punto della regione maledetta è coperto da una regione di esorcismo, e regioni di esorcismo distinte possono incontrarsi solo nei loro estremi.

Quando la posizione centrale è $c$, siano $R(c)$ la lunghezza totale delle regioni di esorcismo rosse e $B(c)$ la lunghezza totale delle regioni di esorcismo blu. La disarmonia di questo rituale di esorcismo è il valore assoluto della differenza tra i due valori, cioè $|R(c) - B(c)|$.

Per aumentare la probabilità di successo del rituale di esorcismo, gli stregoni vogliono scegliere opportunamente la posizione centrale $c$ in modo da minimizzare la disarmonia.

Date le informazioni sugli stregoni e sulle maledizioni lanciate dallo spirito maligno, scrivi un programma che trovi la minima disarmonia del rituale di esorcismo per ciascuna maledizione.

Input

La prima riga contiene il numero di stregoni $N$ e il numero di maledizioni $Q$, separati da uno spazio. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Ciascuna delle successive $N$ righe contiene la coordinata $X_i$ e il colore $C_i$ di uno stregone, separati da uno spazio. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R oppure B)

Ciascuna delle successive $Q$ righe contiene i dati di una maledizione $a, b$, separati da uno spazio. $a$ e $b$ sono gli indici dei due stregoni maledetti dallo spirito maligno. ($1 \le a < b \le N$)

Output

Per ogni maledizione, stampa su una riga separata la minima disarmonia relativa a tale maledizione. Si può dimostrare che la minima disarmonia è sempre un numero intero.

Esempio

Input di esempio 1

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

Output di esempio 1

0
2

Note

Maledizione 1: Se si fissa la posizione centrale a $c = 2.5$, gli intervalli $[1, 2.5]$ e $[8, 12]$ diventano regioni di esorcismo rosse, mentre gli intervalli $[2.5, 6]$ e $[6, 8]$ diventano regioni di esorcismo blu. Poiché la lunghezza totale delle regioni di esorcismo rosse e la lunghezza totale delle regioni di esorcismo blu sono entrambe pari a $5.5$, la disarmonia è $0$. Anche fissando la posizione centrale a $c = 11.5$ la disarmonia risulta $0$.

Maledizione 2: Se si fissa la posizione centrale a $c = 8$, l'intero intervallo $[6, 8]$ diventa una regione di esorcismo blu. Poiché non ci sono stregoni rossi nella regione maledetta, non è possibile rendere la disarmonia minore di $2$.