רוח רעה חדרה לרחוב מסוים בשינג'וקו. רחוב זה הוא בצורת קטע המחבר בין כניסה בקצה השמאלי ליציאה בקצה הימני, והמרחק בין שתי נקודות הקצה הוא $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$.