JOIG Tour

Just Odd Ink Way라는 길을 아는가. EGOI 공화국의 동쪽 끝에서 서쪽 끝까지 이어진 길이 $10^{100}$인 국도다. 길을 따라 "Just Odd Ink"가 그린 그림이 여러 점 있는 것으로 유명하다. 이하에서는 JOI Way라고 부른다.

JOI Way에는 크기가 다른 그림이 여러 점 있다. 그중 일부에는 글자가 적혀 있다.

Rie는 JOI Way의 관광 안내원이다. 그녀는 JOIG 봄 훈련 캠프 참가자들을 안내할 계획이다. 참가자들을 격려하려고 'J', 'O', 'I', 'G'가 적힌 그림을 골라 이 순서대로 방문하려 한다. 후보 그림은 $N$점이다. $i$번째 그림($1 \le i \le N$)은 서쪽 끝에서 $A_i$만큼 떨어진 곳에 있고, 여기에는 문자 $C_i$가 적혀 있다.

Rie에게는 $Q$개의 계획이 있다. $j$번째 계획($1 \le j \le Q$)에서 그녀는 다음과 같이 이동한다.

1. Rie는 서쪽 끝에서 $S_j$만큼 떨어진 곳에서 출발한다.
2. 'J'가 적힌 그림을 골라 그 위치로 이동한다.
3. 'O'가 적힌 그림을 골라 그 위치로 이동한다.
4. 'I'가 적힌 그림을 골라 그 위치로 이동한다.
5. 'G'가 적힌 그림을 골라 그 위치로 이동한다.
6. 서쪽 끝에서 $T_j$만큼 떨어진 곳으로 이동하고 투어를 마친다.

JOI Way 밖으로 나갈 수 없다.

각 계획에 대해 총 이동 거리의 최솟값을 구하라.

입력은 다음 형식으로 주어진다.

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

$Q$줄을 출력한다. $j$번째 줄에는 $j$번째 계획에서 가능한 총 이동 거리의 최솟값을 출력한다.

• $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$)는 'J', 'O', 'I', 'G' 중 하나다.
• 어떤 $i$에 대해서는 $C_i$가 'J'다 ($1 \le i \le N$).
• 어떤 $i$에 대해서는 $C_i$가 'O'다 ($1 \le i \le N$).
• 어떤 $i$에 대해서는 $C_i$가 'I'다 ($1 \le i \le N$).
• 어떤 $i$에 대해서는 $C_i$가 'G'다 ($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$는 정수다.