Shinjukun eräälle kadulle on tunkeutunut paha henki. Tämä katu on janan muotoinen ja yhdistää vasemmassa päässä olevan sisäänkäynnin ja oikeassa päässä olevan uloskäynnin, ja päätepisteiden välinen etäisyys on $10^9 + 1$.

Kadulla on $N$ manaajaa. Manaajilla on kokonaislukunumerot väliltä $1$ ja $N$ sen mukaan, kuinka lähellä sisäänkäyntiä he ovat. Manaaja $i$ on etäisyydellä $X_i$ ($X_i$ on positiivinen kokonaisluku) sisäänkäynnistä oikealle, ja kaikki manaajat ovat eri kohdissa. Lisäksi jokaisella manaajalla on jompikumpi kahdesta väristä: punainen tai sininen.

Jokainen kirous annetaan kahdella kokonaisluvulla $a, b$. Paha henki langettaa kirouksen manaajille $a$ ja $b$, ja aina pätee $1 \le a < b \le N$. Tällöin kahta manaajaa yhdistävälle janalle muodostuu kirottu alue, joka on väli $[X_a, X_b]$.

Kun kirottu alue muodostuu, manaajat valitsevat kirotulta alueelta yhden pisteen ja asettavat sen ydinsijainniksi. Ydinsijainnin koordinaatti voi olla reaaliluku. Merkitään ydinsijaintia $c$:llä. Ydinsijainti saa olla sama kuin manaajan sijainti.

Kun ydinsijainti on päätetty, kirottu alue jaetaan punaisiin karkotusalueisiin ja sinisiin karkotusalueisiin seuraavien sääntöjen mukaisesti.

Tarkastellaan jokaisella $a \le i < b$ kahden vierekkäisen manaajan välistä väliä $[X_i, X_{i+1}]$.

• Jos $X_{i+1} \le c$, koko välistä $[X_i, X_{i+1}]$ tulee manaajan $i$ värinen karkotusalue.
• Jos $c \le X_i$, koko välistä $[X_i, X_{i+1}]$ tulee manaajan $i+1$ värinen karkotusalue.
• Jos $X_i < c < X_{i+1}$, välistä $[X_i, c]$ tulee manaajan $i$ värinen karkotusalue, ja välistä $[c, X_{i+1}]$ tulee manaajan $i+1$ värinen karkotusalue.

Toisin sanoen ydinsijainnista $c$ katsottuna vasemmalla puolella oleva osa noudattaa vasemmassa päätepisteessä olevan manaajan väriä, ja oikealla puolella oleva osa noudattaa oikeassa päätepisteessä olevan manaajan väriä.

Yllä olevien sääntöjen nojalla kirotun alueen jokainen piste peittyy karkotusalueella, ja eri karkotusalueet voivat kohdata vain päätepisteissään.

Kun ydinsijainti on $c$, olkoon punaisten karkotusalueiden kokonaispituus $R(c)$ ja sinisten karkotusalueiden kokonaispituus $B(c)$. Tämän karkotusrituaalin epäsointu on näiden kahden arvon erotuksen itseisarvo eli $|R(c) - B(c)|$.

Kasvattaakseen karkotusrituaalin onnistumistodennäköisyyttä manaajat haluavat valita ydinsijainnin $c$ sopivasti niin, että epäsointu minimoituu.

Kun manaajien tiedot sekä pahan hengen langettamien kirousten tiedot annetaan, kirjoita ohjelma, joka etsii jokaiselle kiroukselle karkotusrituaalin pienimmän mahdollisen epäsoinnun.

Syöte

Ensimmäisellä rivillä annetaan manaajien lukumäärä $N$ ja kirousten lukumäärä $Q$ välilyönnillä erotettuina. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Toiselta riviltä alkaen $N$ rivillä annetaan manaajan koordinaatti $X_i$ ja väri $C_i$ välilyönnillä erotettuina. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R tai B)

Seuraavalta riviltä alkaen $Q$ rivillä annetaan kirouksen sisältö $a, b$ välilyönnillä erotettuina. $a$ ja $b$ ovat niiden kahden manaajan numerot, joille paha henki langettaa kirouksen. ($1 \le a < b \le N$)

Tuloste

Tulosta jokaiselle kiroukselle omalle rivilleen kyseisen kirouksen pienin mahdollinen epäsointu. Voidaan todistaa, että pienin epäsointu on aina kokonaisluku.

Esimerkit

Syöte 1

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

Tuloste 1

0
2

Huomautus

Kirous 1: Jos ydinsijainniksi asetetaan $c = 2.5$, väleistä $[1, 2.5]$ ja $[8, 12]$ tulee punaisia karkotusalueita, ja väleistä $[2.5, 6]$ ja $[6, 8]$ tulee sinisiä karkotusalueita. Koska punaisten karkotusalueiden kokonaispituus ja sinisten karkotusalueiden kokonaispituus ovat molemmat $5.5$, epäsointu on $0$. Vaikka ydinsijainniksi asetettaisiin $c = 11.5$, epäsointu on $0$.

Kirous 2: Jos ydinsijainniksi asetetaan $c = 8$, koko välistä $[6, 8]$ tulee sininen karkotusalue. Koska kirotulla alueella ei ole punaista manaajaa, epäsointua ei voida saada pienemmäksi kuin $2$.