تسللت روح شريرة إلى أحد شوارع شينجوكو. هذا الشارع له شكل قطعة مستقيمة تصل بين المدخل عند الطرف الأيسر والمخرج عند الطرف الأيمن، والمسافة بين الطرفين هي $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$.