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