วิญญาณร้ายได้แทรกซึมเข้ามาในถนนสายหนึ่งในชินจูกุ ถนนสายนี้มีลักษณะเป็นส่วนของเส้นตรงที่เชื่อมทางเข้าที่ปลายด้านซ้ายกับทางออกที่ปลายด้านขวา และระยะห่างระหว่างจุดปลายทั้งสองคือ $10^9 + 1$

มีผู้ใช้คุณไสย $N$ คนอยู่บนถนน ผู้ใช้คุณไสยมีหมายเลขประจำตัวเป็นจำนวนเต็มตั้งแต่ $1$ ถึง $N$ ตามลำดับความใกล้จากทางเข้า ผู้ใช้คุณไสยหมายเลข $i$ อยู่ทางขวาของทางเข้าเป็นระยะ $X_i$ ($X_i$ เป็นจำนวนเต็มบวก) และผู้ใช้คุณไสยทุกคนอยู่ในตำแหน่งที่แตกต่างกัน นอกจากนี้ผู้ใช้คุณไสยแต่ละคนจะมีสีใดสีหนึ่งระหว่างสีแดงหรือสีน้ำเงิน

คำสาปแต่ละครั้งกำหนดด้วยจำนวนเต็มสองจำนวน $a, b$ วิญญาณร้ายจะสาปผู้ใช้คุณไสยหมายเลข $a$ และ $b$ โดยที่ $1 \le a < b \le N$ เสมอ เมื่อนั้นจะเกิดเขตคำสาปขึ้นบนส่วนของเส้นตรงที่เชื่อมผู้ใช้คุณไสยทั้งสอง โดยเขตคำสาปคือช่วง $[X_a, X_b]$

เมื่อเขตคำสาปถูกสร้างขึ้น เหล่าผู้ใช้คุณไสยจะเลือกจุดหนึ่งบนเขตคำสาปเพื่อกำหนดเป็นตำแหน่งแกนกลาง พิกัดของตำแหน่งแกนกลางอาจเป็นจำนวนจริงได้ ให้ตำแหน่งแกนกลางคือ $c$ ตำแหน่งแกนกลางอาจตรงกับตำแหน่งที่มีผู้ใช้คุณไสยอยู่ก็ได้

เมื่อกำหนดตำแหน่งแกนกลางแล้ว เขตคำสาปจะถูกแบ่งออกเป็นเขตปัดเป่าสีแดงและเขตปัดเป่าสีน้ำเงินตามกฎต่อไปนี้

สำหรับแต่ละ $a \le i < b$ ให้พิจารณาช่วง $[X_i, X_{i+1}]$ ระหว่างผู้ใช้คุณไสยสองคนที่อยู่ติดกัน

• ถ้า $X_{i+1} \le c$ ช่วง $[X_i, X_{i+1}]$ ทั้งหมดจะกลายเป็นเขตปัดเป่าที่มีสีตามผู้ใช้คุณไสยหมายเลข $i$
• ถ้า $c \le X_i$ ช่วง $[X_i, X_{i+1}]$ ทั้งหมดจะกลายเป็นเขตปัดเป่าที่มีสีตามผู้ใช้คุณไสยหมายเลข $i+1$
• ถ้า $X_i < c < X_{i+1}$ ช่วง $[X_i, c]$ จะกลายเป็นเขตปัดเป่าที่มีสีตามผู้ใช้คุณไสยหมายเลข $i$ และช่วง $[c, X_{i+1}]$ จะกลายเป็นเขตปัดเป่าที่มีสีตามผู้ใช้คุณไสยหมายเลข $i+1$

กล่าวคือ เมื่อยึดตำแหน่งแกนกลาง $c$ เป็นหลัก ส่วนที่อยู่ทางซ้ายจะใช้สีของผู้ใช้คุณไสยที่จุดปลายด้านซ้าย และส่วนที่อยู่ทางขวาจะใช้สีของผู้ใช้คุณไสยที่จุดปลายด้านขวา

ตามกฎข้างต้น ทุกจุดในเขตคำสาปจะถูกครอบคลุมด้วยเขตปัดเป่า และเขตปัดเป่าที่ต่างกันสามารถบรรจบกันได้ที่จุดปลายเท่านั้น

เมื่อตำแหน่งแกนกลางคือ $c$ ให้ความยาวรวมของเขตปัดเป่าสีแดงคือ $R(c)$ และความยาวรวมของเขตปัดเป่าสีน้ำเงินคือ $B(c)$ ความไม่สอดคล้องของพิธีปัดเป่านี้คือค่าสัมบูรณ์ของผลต่างของค่าทั้งสอง ซึ่งก็คือ $|R(c) - B(c)|$

เพื่อเพิ่มอัตราความสำเร็จของพิธีปัดเป่า เหล่าผู้ใช้คุณไสยจึงต้องการเลือกตำแหน่งแกนกลาง $c$ อย่างเหมาะสมเพื่อให้ความไม่สอดคล้องมีค่าน้อยที่สุด

เมื่อกำหนดข้อมูลของผู้ใช้คุณไสยและข้อมูลการสาปของวิญญาณร้าย จงเขียนโปรแกรมเพื่อหาความไม่สอดคล้องที่น้อยที่สุดของพิธีปัดเป่าสำหรับแต่ละคำสาป

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนผู้ใช้คุณไสย $N$ และจำนวนคำสาป $Q$ คั่นด้วยช่องว่าง ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

ตั้งแต่บรรทัดที่สองเป็นต้นไปจำนวน $N$ บรรทัด แต่ละบรรทัดประกอบด้วยพิกัด $X_i$ และสี $C_i$ ของผู้ใช้คุณไสย คั่นด้วยช่องว่าง ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R หรือ B)

ถัดมาอีก $Q$ บรรทัด แต่ละบรรทัดประกอบด้วยข้อมูลคำสาป $a, b$ คั่นด้วยช่องว่าง โดย $a$ และ $b$ คือหมายเลขของผู้ใช้คุณไสยสองคนที่ถูกวิญญาณร้ายสาป ($1 \le a < b \le N$)

ข้อมูลส่งออก

สำหรับแต่ละคำสาป ให้พิมพ์ความไม่สอดคล้องที่น้อยที่สุดสำหรับคำสาปนั้นบรรทัดละหนึ่งค่า สามารถพิสูจน์ได้ว่าความไม่สอดคล้องที่น้อยที่สุดเป็นจำนวนเต็มเสมอ

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

0
2

หมายเหตุ

คำสาปที่ 1: หากกำหนดตำแหน่งแกนกลางเป็น $c = 2.5$ ช่วง $[1, 2.5]$ และ $[8, 12]$ จะกลายเป็นเขตปัดเป่าสีแดง และช่วง $[2.5, 6]$ และ $[6, 8]$ จะกลายเป็นเขตปัดเป่าสีน้ำเงิน เนื่องจากความยาวรวมของเขตปัดเป่าสีแดงและความยาวรวมของเขตปัดเป่าสีน้ำเงินต่างก็เท่ากับ $5.5$ ความไม่สอดคล้องจึงเป็น $0$ ต่อให้กำหนดตำแหน่งแกนกลางเป็น $c = 11.5$ ความไม่สอดคล้องก็เป็น $0$ เช่นกัน

คำสาปที่ 2: หากกำหนดตำแหน่งแกนกลางเป็น $c = 8$ ช่วง $[6, 8]$ ทั้งหมดจะกลายเป็นเขตปัดเป่าสีน้ำเงิน เนื่องจากไม่มีผู้ใช้คุณไสยสีแดงในเขตคำสาป จึงไม่สามารถทำให้ความไม่สอดคล้องน้อยกว่า $2$ ได้