JOIG Tour

Do you know Just Odd Ink Way? It is a national road of length $10^{100}$ in Republic of EGOI, running from the east end to the west end. It is famous for several paintings made by "Just Odd Ink" along the road. Below, we call it JOI Way.

Several paintings of various sizes are on JOI Way. Some of them have characters written on them.

Rie is a tour guide on JOI Way. She plans to guide the participants of the JOIG Spring Training Camp. To cheer them up, she will pick paintings with 'J', 'O', 'I', and 'G' written on them, and visit them in this order. There are $N$ candidate paintings. The $i$-th painting ($1 \le i \le N$) is located at distance $A_i$ from the west end, and the character $C_i$ is written on it.

Rie has $Q$ plans. In the $j$-th plan ($1 \le j \le Q$), she travels as follows.

1. Rie starts the tour at the place at distance $S_j$ from the west end.
2. She picks a painting with 'J' written on it and moves to its location.
3. She picks a painting with 'O' written on it and moves to its location.
4. She picks a painting with 'I' written on it and moves to its location.
5. She picks a painting with 'G' written on it and moves to its location.
6. She moves to the place at distance $T_j$ from the west end and ends the tour.

Rie may not go outside JOI Way.

For each plan, find the minimum possible total travel distance.

The input is given in the following format.

$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$

Print $Q$ lines. The $j$-th line contains the minimum possible total travel distance for the $j$-th plan.

• $4 \le N \le 100\,000$.
• $1 \le A_i \le 10^{15}$ ($1 \le i \le N$).
• $A_i < A_{i+1}$ ($1 \le i \le N - 1$).
• $C_i$ ($1 \le i \le N$) is one of 'J', 'O', 'I', or 'G'.
• $C_i$ is 'J' for at least one $i$ ($1 \le i \le N$).
• $C_i$ is 'O' for at least one $i$ ($1 \le i \le N$).
• $C_i$ is 'I' for at least one $i$ ($1 \le i \le N$).
• $C_i$ is 'G' for at least one $i$ ($1 \le i \le N$).
• $1 \le Q \le 100\,000$.
• $1 \le S_j \le 10^{15}$ ($1 \le j \le Q$).
• $1 \le T_j \le 10^{15}$ ($1 \le j \le Q$).
• $(S_j, T_j) \ne (S_k, T_k)$ ($1 \le j < k \le Q$).
• $N$, $Q$, $A_i$, $S_j$, $T_j$ are integers.