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