你知道“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$）位于 JOI Way 上距离西端 $A_i$ 的位置。在这幅画作上，写有字符 $C_i$。

Rie 有 $Q$ 个计划。在第 $j$ 个计划（$1 \le j \le Q$）中，她的行程如下：

1. Rie 从 JOI Way 上距离西端 $S_j$ 的位置开始行程。
2. 她选择一幅写有‘J’的画作，并移动到该位置。
3. 她选择一幅写有‘O’的画作，并移动到该位置。
4. 她选择一幅写有‘I’的画作，并移动到该位置。
5. 她选择一幅写有‘G’的画作，并移动到该位置。
6. 她移动到 JOI Way 上距离西端 $T_j$ 的位置，并结束行程。

在行程中，不允许离开 JOI Way。

在上述条件下，Rie 希望最小化每个计划的总行程距离。

请编写一个程序，在给定 JOI Way 上的画作信息和 Rie 的计划后，计算每个计划的最小可能总行程距离。

输入格式

从标准输入读取以下数据：

$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$ 行（$1 \le j \le Q$）应包含第 $j$ 个计划的最小可能总行程距离。

数据范围

• $4 \le N \le 100\,000$。
• $1 \le A_i \le 1\,000\,000\,000\,000\,000 \ (= 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$ ($1 \le i \le N$) 使得 $C_i$ 为‘J’。
• 至少存在一个 $i$ ($1 \le i \le N$) 使得 $C_i$ 为‘O’。
• 至少存在一个 $i$ ($1 \le i \le N$) 使得 $C_i$ 为‘I’。
• 至少存在一个 $i$ ($1 \le i \le N$) 使得 $C_i$ 为‘G’。
• $1 \le Q \le 100\,000$。
• $1 \le S_j \le 1\,000\,000\,000\,000\,000 \ (= 10^{15})$ ($1 \le j \le Q$)。
• $1 \le T_j \le 1\,000\,000\,000\,000\,000 \ (= 10^{15})$ ($1 \le j \le Q$)。
• $(S_j, T_j) \neq (S_k, T_k)$ ($1 \le j < k \le Q$)。
• $N, Q$ 为整数。
• $A_i$ 为整数 ($1 \le i \le N$)。
• $S_j, T_j$ 为整数 ($1 \le j \le Q$)。

子任务

1. (4 分) $N \le 80, Q \le 10$。
2. (10 分) $N \le 500, Q \le 10$。
3. (6 分) $N \le 3\,000, Q \le 100$。
4. (25 分) $N \le 5\,000, Q \le 1\,000$。
5. (12 分) 存在唯一的 $i$ 使得 $C_i = \text{'O'}$，唯一的 $j$ 使得 $C_j = \text{'I'}$，唯一的 $k$ 使得 $C_k = \text{'G'}$。
6. (8 分) 存在唯一的 $i$ 使得 $C_i = \text{'O'}$，唯一的 $j$ 使得 $C_j = \text{'I'}$。
7. (20 分) 存在唯一的 $i$ 使得 $C_i = \text{'O'}$。
8. (15 分) 无附加限制。

样例

样例输入 1

7
1 J
2 O
3 G
4 I
5 O
8 G
10 J
2
3 2
7 5

样例输出 1

7
12

样例输入 2

10
5 J
7 O
10 J
11 G
12 J
13 I
17 J
18 J
19 J
20 J
4
4 9
15 14
6 20
7 20

样例输出 2

13
19
20
21

样例输入 3

10
1 G
2 J
3 G
4 O
7 G
9 J
10 G
14 I
17 G
19 G
7
11 6
6 3
17 19
1 18
17 17
20 1
20 10

样例输出 3

25
27
28
17
26
39
30

样例输入 4

10
3 J
5 G
6 I
7 I
8 J
9 I
10 O
14 G
16 I
19 J
6
4 4
20 3
18 5
15 4
20 11
10 8

样例输出 4

12
17
15
15
19
12

样例输入 5

12
179948747891578 I
263779425244614 I
320153642407146 G
383698990675423 J
478483318441339 J
505589213620811 G
507468309040564 O
530441288489671 J
730036011088087 O
896127332008998 I
899298512463927 O
915990785839829 J
10
744829561026263 366031656398270
700496830781726 684771674298690
314138534887378 222241904398827
695615197615084 632164325876673
418419052313523 409258287819812
932490604948180 62799105708059
738126150487131 45378717857226
320047965627255 918203067583346
859632377126681 967370566306944
115848334010451 834089404672067

样例输出 5

583302366935305
805077987955000
591304613119987
757352272699625
478217003098189
869691499240121
805495866954969
1085532869547991
928541333618299
1205618838253516