Một ác linh đã xâm nhập vào một con phố ở Shinjuku. Con phố này có hình dạng một đoạn thẳng nối lối vào ở đầu bên trái với lối ra ở đầu bên phải, và khoảng cách giữa hai đầu mút là $10^9 + 1$.

Có $N$ chú thuật sư đang ở trên phố. Các chú thuật sư được đánh số nguyên từ $1$ đến $N$ theo thứ tự tăng dần khoảng cách từ lối vào. Chú thuật sư thứ $i$ nằm cách lối vào một khoảng $X_i$ ($X_i$ là một số nguyên dương) về phía bên phải, và tất cả các chú thuật sư đều ở các vị trí khác nhau. Ngoài ra, mỗi chú thuật sư mang một trong hai màu: đỏ hoặc xanh.

Mỗi lời nguyền được cho bởi hai số nguyên $a, b$. Ác linh ếm lời nguyền lên chú thuật sư thứ $a$ và thứ $b$, luôn thỏa mãn $1 \le a < b \le N$. Khi đó, một vùng bị nguyền rủa được tạo ra trên đoạn thẳng nối hai chú thuật sư, và vùng bị nguyền rủa là đoạn $[X_a, X_b]$.

Khi vùng bị nguyền rủa được tạo ra, các chú thuật sư chọn một điểm trên vùng bị nguyền rủa làm vị trí cốt lõi. Tọa độ của vị trí cốt lõi có thể là một số thực. Gọi vị trí cốt lõi là $c$. Vị trí cốt lõi có thể trùng với vị trí của một chú thuật sư.

Sau khi vị trí cốt lõi được chọn, vùng bị nguyền rủa được chia thành các vùng trừ tà màu đỏ và vùng trừ tà màu xanh theo quy tắc sau.

Với mỗi $a \le i < b$, xét đoạn $[X_i, X_{i+1}]$ giữa hai chú thuật sư liền kề.

• Nếu $X_{i+1} \le c$, toàn bộ đoạn $[X_i, X_{i+1}]$ trở thành vùng trừ tà mang màu của chú thuật sư thứ $i$.
• Nếu $c \le X_i$, toàn bộ đoạn $[X_i, X_{i+1}]$ trở thành vùng trừ tà mang màu của chú thuật sư thứ $i+1$.
• Nếu $X_i < c < X_{i+1}$, đoạn $[X_i, c]$ trở thành vùng trừ tà mang màu của chú thuật sư thứ $i$, và đoạn $[c, X_{i+1}]$ trở thành vùng trừ tà mang màu của chú thuật sư thứ $i+1$.

Nói cách khác, lấy vị trí cốt lõi $c$ làm chuẩn, phần bên trái tuân theo màu của chú thuật sư ở đầu mút bên trái, còn phần bên phải tuân theo màu của chú thuật sư ở đầu mút bên phải.

Theo quy tắc trên, mọi điểm trong vùng bị nguyền rủa đều được bao phủ bởi vùng trừ tà, và các vùng trừ tà khác nhau chỉ có thể giao nhau tại các đầu mút.

Khi vị trí cốt lõi là $c$, gọi tổng độ dài của các vùng trừ tà màu đỏ là $R(c)$ và tổng độ dài của các vùng trừ tà màu xanh là $B(c)$. Độ bất hòa của nghi thức trừ tà này là giá trị tuyệt đối của hiệu hai giá trị đó, tức là $|R(c) - B(c)|$.

Để tăng tỷ lệ thành công của nghi thức trừ tà, các chú thuật sư muốn chọn vị trí cốt lõi $c$ một cách thích hợp nhằm cực tiểu hóa độ bất hòa.

Cho thông tin về các chú thuật sư và các lời nguyền do ác linh gây ra, hãy viết chương trình tìm độ bất hòa nhỏ nhất của nghi thức trừ tà đối với mỗi lời nguyền.

Dữ liệu vào

Dòng đầu tiên chứa số lượng chú thuật sư $N$ và số lượng lời nguyền $Q$, cách nhau bởi một khoảng trắng. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Trong $N$ dòng tiếp theo, mỗi dòng chứa tọa độ $X_i$ và màu $C_i$ của một chú thuật sư, cách nhau bởi một khoảng trắng. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R hoặc B)

Trong $Q$ dòng tiếp theo, mỗi dòng chứa thông tin lời nguyền $a, b$, cách nhau bởi một khoảng trắng. $a$ và $b$ là số hiệu của hai chú thuật sư bị ác linh nguyền rủa. ($1 \le a < b \le N$)

Dữ liệu ra

Với mỗi lời nguyền, in ra trên một dòng độ bất hòa nhỏ nhất tương ứng với lời nguyền đó. Có thể chứng minh rằng độ bất hòa nhỏ nhất luôn là một số nguyên.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
2

Ghi chú

Lời nguyền 1: Nếu chọn vị trí cốt lõi là $c = 2.5$, các đoạn $[1, 2.5]$ và $[8, 12]$ trở thành vùng trừ tà màu đỏ, còn các đoạn $[2.5, 6]$ và $[6, 8]$ trở thành vùng trừ tà màu xanh. Tổng độ dài của vùng trừ tà màu đỏ và vùng trừ tà màu xanh đều bằng $5.5$, nên độ bất hòa là $0$. Chọn vị trí cốt lõi là $c = 11.5$ cũng cho độ bất hòa bằng $0$.

Lời nguyền 2: Nếu chọn vị trí cốt lõi là $c = 8$, toàn bộ đoạn $[6, 8]$ trở thành vùng trừ tà màu xanh. Vì không có chú thuật sư màu đỏ nào trong vùng bị nguyền rủa, độ bất hòa không thể nhỏ hơn $2$.