新宿嘅某條街道被惡靈滲透咗。呢條街道呈連接左端入口同右端出口嘅線段形狀，兩個端點之間嘅距離係 $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$。