На одну из улиц Синдзюку проник злой дух. Эта улица имеет форму отрезка, соединяющего вход на левом конце и выход на правом конце, а расстояние между двумя концами равно $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$ невозможно.