新宿的某条街道被恶灵渗透了。这条街道呈连接左端入口与右端出口的线段形状，两个端点之间的距离为 $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$。