新宿のある通りに悪霊が入り込んだ。この通りは左端にある入口と右端にある出口を結ぶ線分の形をしており、両端点の間の距離は $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$ を適切に選んで不調和度を最小化しようとしている。

呪術師の情報と悪霊が呪いをかける情報が与えられたとき、各呪いに対する退魔儀式の最小不調和度を求めるプログラムを作成せよ。

入力

1 行目には呪術師の数 $N$ と呪いの数 $Q$ が空白区切りで与えられる。（$2 \le N \le 200\,000$; $1 \le Q \le 200\,000$）

2 行目からの $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 行に 1 つずつ、その呪いに対する最小不調和度を出力する。最小不調和度は常に整数であることが証明できる。

入出力例

入力例 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$ より小さくすることはできない。