Roh jahat telah menyusup ke sebuah jalan di Shinjuku. Jalan ini berbentuk ruas garis yang menghubungkan pintu masuk di ujung kiri dan pintu keluar di ujung kanan, serta jarak antara kedua titik ujung tersebut adalah $10^9 + 1$.

Terdapat $N$ penyihir jujutsu di jalan tersebut. Para penyihir diberi nomor bilangan bulat dari $1$ hingga $N$ sesuai urutan kedekatan dari pintu masuk. Penyihir ke-$i$ berada sejauh $X_i$ ($X_i$ adalah bilangan bulat positif) di sebelah kanan pintu masuk, dan semua penyihir berada di posisi yang berbeda-beda. Selain itu, setiap penyihir memiliki salah satu dari dua warna: merah atau biru.

Setiap kutukan diberikan sebagai dua bilangan bulat $a, b$. Roh jahat mengutuk penyihir ke-$a$ dan ke-$b$, dengan $1 \le a < b \le N$ selalu terpenuhi. Saat itu, wilayah kutukan terbentuk pada ruas garis yang menghubungkan kedua penyihir tersebut, dan wilayah kutukan tersebut adalah interval $[X_a, X_b]$.

Ketika wilayah kutukan terbentuk, para penyihir memilih satu titik pada wilayah kutukan untuk ditetapkan sebagai posisi inti. Koordinat posisi inti boleh berupa bilangan riil. Misalkan posisi inti adalah $c$. Posisi inti boleh sama dengan posisi tempat seorang penyihir berada.

Setelah posisi inti ditetapkan, wilayah kutukan dibagi menjadi wilayah pengusiran merah dan wilayah pengusiran biru sesuai aturan berikut.

Untuk setiap $a \le i < b$, tinjau interval $[X_i, X_{i+1}]$ di antara dua penyihir yang bersebelahan.

• Jika $X_{i+1} \le c$, seluruh interval $[X_i, X_{i+1}]$ menjadi wilayah pengusiran dengan warna milik penyihir ke-$i$.
• Jika $c \le X_i$, seluruh interval $[X_i, X_{i+1}]$ menjadi wilayah pengusiran dengan warna milik penyihir ke-$i+1$.
• Jika $X_i < c < X_{i+1}$, interval $[X_i, c]$ menjadi wilayah pengusiran dengan warna milik penyihir ke-$i$, dan interval $[c, X_{i+1}]$ menjadi wilayah pengusiran dengan warna milik penyihir ke-$i+1$.

Dengan kata lain, relatif terhadap posisi inti $c$, bagian di sebelah kiri mengikuti warna penyihir di titik ujung kiri, sedangkan bagian di sebelah kanan mengikuti warna penyihir di titik ujung kanan.

Berdasarkan aturan di atas, setiap titik di wilayah kutukan tertutup oleh wilayah pengusiran, dan wilayah pengusiran yang berbeda hanya dapat bertemu di titik-titik ujungnya.

Ketika posisi inti adalah $c$, misalkan total panjang wilayah pengusiran merah adalah $R(c)$ dan total panjang wilayah pengusiran biru adalah $B(c)$. Ketidakselarasan dari ritual pengusiran ini adalah nilai mutlak dari selisih kedua nilai tersebut, yaitu $|R(c) - B(c)|$.

Untuk meningkatkan tingkat keberhasilan ritual pengusiran, para penyihir ingin memilih posisi inti $c$ secara tepat agar ketidakselarasan menjadi minimum.

Diberikan informasi mengenai para penyihir dan kutukan yang dilancarkan oleh roh jahat, buatlah program untuk mencari ketidakselarasan minimum dari ritual pengusiran untuk setiap kutukan.

Masukan

Baris pertama berisi banyaknya penyihir $N$ dan banyaknya kutukan $Q$ yang dipisahkan oleh spasi. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Dari baris kedua sebanyak $N$ baris, masing-masing berisi koordinat penyihir $X_i$ dan warna $C_i$ yang dipisahkan oleh spasi. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R atau B)

Sebanyak $Q$ baris berikutnya berisi rincian kutukan $a, b$ yang dipisahkan oleh spasi. $a$ dan $b$ adalah nomor dua penyihir yang dikutuk oleh roh jahat. ($1 \le a < b \le N$)

Keluaran

Untuk setiap kutukan, cetak satu nilai per baris yang menyatakan ketidakselarasan minimum untuk kutukan tersebut. Dapat dibuktikan bahwa ketidakselarasan minimum selalu berupa bilangan bulat.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

0
2

Catatan

Kutukan 1: Jika posisi inti ditetapkan sebagai $c = 2.5$, interval $[1, 2.5]$ dan $[8, 12]$ menjadi wilayah pengusiran merah, sedangkan interval $[2.5, 6]$ dan $[6, 8]$ menjadi wilayah pengusiran biru. Karena total panjang wilayah pengusiran merah dan total panjang wilayah pengusiran biru keduanya adalah $5.5$, maka ketidakselarasannya adalah $0$. Menetapkan posisi inti sebagai $c = 11.5$ juga menghasilkan ketidakselarasan $0$.

Kutukan 2: Jika posisi inti ditetapkan sebagai $c = 8$, seluruh interval $[6, 8]$ menjadi wilayah pengusiran biru. Karena tidak ada penyihir merah di wilayah kutukan, ketidakselarasan tidak dapat dibuat lebih kecil dari $2$.