신주쿠의 어느 거리에 악령이 스며들었다. 이 거리는 왼쪽 끝에 있는 입구와 오른쪽 끝에 있는 출구를 잇는 선분 모양이며, 두 끝점 사이 거리는 $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 or 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$보다 작게 할 수 없다.