JOIG Tour

Do you know Just Odd Ink Way? It is a national road of length $10^{100}$ in Republic of EGOI from the east end to the west end. It is famous because there are several painting on the road painted by “Just Odd Ink.” In the following, we abbreviate it, and call it JOI Way.

There are several painting of various sizes on JOI Way. Characters are written on some of them.

Rie is a tour guide working on JOI Way. She plans to guide the participants of JOIG Spring Training Camp. In order to cheer the participants, she plans to choose the paintings on which ‘J’, ‘O’, ‘I’, ‘G’ are written, and visit them in this order. There are $N$ candidates of paintings. The $i$-th painting ($1 ≤ i ≤ N$) is located at the place on JOI Way at a distance of $A\_i$ from the west end. In this painting, the character $C\_i$ is written.

Rie has $Q$ plans. In the $j$-th plan ($1 ≤ j ≤ Q$), she will travel as follows.

1. Rie starts a tour from the place on JOI Way at a distance of $S\_j$ from the west end.
2. She chooses a painting on which ‘J’ is written, and moves to its location.
3. She chooses a painting on which ‘O’ is written, and moves to its location.
4. She chooses a painting on which ‘I’ is written, and moves to its location.
5. She chooses a painting on which ‘G’ is written, and moves to its location.
6. She moves to the place on JOI Way at a distance of $T\_j$ from the west end, and finishes the tour.

During the tour, it is not allowed to go outside JOI Way.

Under the above conditions, Rie wants to minimize the total travel distance for each plan.

Write a program which, given information on the paintings on JOI Way and Rie’s plans, calculates the minimum possible value of the total travel distance for each plan.

Read the following data from the standard input.

$N$

$A\_1$ $C\_1$

$A\_2$ $C\_2$

$\vdots$

$A\_N$ $C\_N$

$Q$

$S\_1$ $T\_1$

$S\_2$ $T\_2$

$\vdots$

$S\_Q$ $T\_Q$

Write $Q$ lines to the standard output. The $j$-th line ($1 ≤ j ≤ Q$) of the output should contain the minimum possible value of the total travel distance for the $j$-th plan.

• $4 ≤ N ≤ 100\\,000$.
• $1 ≤ A\_i ≤ 1\\,000\\,000\\,000\\,000\\,000 (= 10^{15})$ ($1 ≤ i ≤ N$).
• $A\_i < A\_{i+1}$ ($1 ≤ i ≤ N - 1$).
• $C\_i$ ($1 ≤ i ≤ N$) is either ‘J’，‘O’，‘I’，or ‘G’.
• $C\_i$ is equal to ‘J’ for at least one $i$ ($1 ≤ i ≤ N$).
• $C\_i$ is equal to ‘O’ for at least one $i$ ($1 ≤ i ≤ N$).
• $C\_i$ is equal to ‘I’ for at least one $i$ ($1 ≤ i ≤ N$).
• $C\_i$ is equal to ‘G’ for at least one $i$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 100\\,000$.
• $1 ≤ S\_j ≤ 1\\,000\\,000\\,000\\,000\\,000 (= 10^{15})$ ($1 ≤ j ≤ Q$).
• $1 ≤ T\_j ≤ 1\\,000\\,000\\,000\\,000\\,000 (= 10^{15})$ ($1 ≤ j ≤ Q$).
• $(S\_j , T\_j) \ne (S\_k, T\_k)$ ($1 ≤ j < k ≤ Q$).
• $N$, $Q$ are integers.
• $A\_i$ is an integer ($1 ≤ i ≤ N$).
• $S\_j$, $T\_j$ are integers ($1 ≤ j ≤ Q$).