An evil spirit has infiltrated a street in Shinjuku. The street is shaped like a line segment connecting an entrance at its left endpoint to an exit at its right endpoint, and the distance between the two endpoints is $10^9 + 1$.

There are $N$ sorcerers on the street. They are numbered with integers from $1$ to $N$ in increasing order of distance from the entrance. Sorcerer $i$ is located $X_i$ ($X_i$ is a positive integer) units to the right of the entrance, and all sorcerers are at distinct positions. Each sorcerer is also assigned one of two colors: red or blue.

Each curse is specified by two integers $a, b$. The evil spirit curses sorcerers $a$ and $b$, where $1 \le a < b \le N$ always holds. A cursed region is then created on the line segment connecting the two sorcerers; that is, the cursed region is the interval $[X_a, X_b]$.

Once the cursed region is created, the sorcerers choose a point within it as the core position. The coordinate of the core position may be a real number. Let the core position be $c$. The core position may coincide with the position of a sorcerer.

After the core position is chosen, the cursed region is divided into red and blue exorcism regions according to the following rules.

For each $a \le i < b$, consider the interval $[X_i, X_{i+1}]$ between two adjacent sorcerers.

• If $X_{i+1} \le c$, the entire interval $[X_i, X_{i+1}]$ becomes an exorcism region of the same color as sorcerer $i$.
• If $c \le X_i$, the entire interval $[X_i, X_{i+1}]$ becomes an exorcism region of the same color as sorcerer $i+1$.
• If $X_i < c < X_{i+1}$, the interval $[X_i, c]$ becomes an exorcism region of the same color as sorcerer $i$, while the interval $[c, X_{i+1}]$ becomes an exorcism region of the same color as sorcerer $i+1$.

In other words, relative to the core position $c$, the portion on the left follows the color of the sorcerer at the left endpoint, while the portion on the right follows the color of the sorcerer at the right endpoint.

Under these rules, every point in the cursed region is covered by an exorcism region, and distinct exorcism regions may meet only at their endpoints.

When the core position is $c$, let $R(c)$ be the total length of the red exorcism regions and $B(c)$ be the total length of the blue exorcism regions. The disharmony of the exorcism ritual is the absolute difference between these two values, namely $|R(c) - B(c)|$.

To increase the ritual's chance of success, the sorcerers want to choose the core position $c$ appropriately so that the disharmony is minimized.

Given the information about the sorcerers and the curses cast by the evil spirit, write a program that finds the minimum possible disharmony for each curse.

Input

The first line contains two integers $N$ and $Q$, the number of sorcerers and the number of curses, respectively, separated by a space. ($2 \le N \le 200\,000$; $1 \le Q \le 200\,000$)

Each of the next $N$ lines contains the coordinate $X_i$ and the color $C_i$ of a sorcerer, separated by a space. ($1 \le X_1 < X_2 < \dots < X_N \le 10^9$, $C_i =$ R or B)

Each of the following $Q$ lines contains two integers $a, b$, describing a curse, separated by a space. $a$ and $b$ are the indices of the two sorcerers cursed by the evil spirit. ($1 \le a < b \le N$)

Output

For each curse, print the minimum possible disharmony on a separate line. It can be proven that the minimum disharmony is always an integer.

Examples

Sample Input 1

4 2
1 R
6 B
8 B
12 R
1 4
2 3

Sample Output 1

0
2

Note

Curse 1: If the core position is chosen as $c = 2.5$, the intervals $[1, 2.5]$ and $[8, 12]$ become red exorcism regions, while the intervals $[2.5, 6]$ and $[6, 8]$ become blue exorcism regions. The total lengths of the red and blue exorcism regions are both $5.5$, so the disharmony is $0$. Choosing $c = 11.5$ also results in a disharmony of $0$.

Curse 2: If the core position is chosen as $c = 8$, the entire interval $[6, 8]$ becomes a blue exorcism region. Since there is no red sorcerer in the cursed region, the disharmony cannot be made smaller than $2$.