The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG TourJOIG ツアー (JOIG Tour)
あなたは Just Odd Ink 街道を知っているだろうか？この街道は EGOI 国を東西に横断する長さ 10100 の街道であり，「ただ奇妙なインク (just odd ink)」によって描かれたたくさんのアートで有名である．ここでは略して JOI 街道と呼ぶ．
さて，JOI 街道には大小様々なアートが描かれているが，そのうちいくつかは文字が描かれているように見える．

JOI 街道のツアーガイドである理恵さんは，JOIG 春合宿の参加者を案内することになった．JOIG 春合宿の参加者を喜ばせたい理恵さんは，JOI 街道に描かれているアートのうち，‘J’, ‘O’, ‘I’, ‘G’ と読めるアート
をこの順に訪れるツアーの計画を考えている．訪れる候補となるアートは N 個あり，i 番目 (1 ≦ i ≦ N) のアートは JOI 街道の西端から距離 Ai の地点にあり，このアートは Ci と読める．
理恵さんは Q 個の計画を考えている． j 番目 (1 ≦ j ≦ Q) の計画におけるツアーでは，以下の順に移動を行う．

1. JOI 街道の西端から距離 S j の地点からツアーを開始する．
2. ‘J’ と読めるアートがある地点を 1 つ選び，その地点に移動する．
3. ‘O’ と読めるアートがある地点を 1 つ選び，その地点に移動する．
4. ‘I’ と読めるアートがある地点を 1 つ選び，その地点に移動する．
5. ‘G’ と読めるアートがある地点を 1 つ選び，その地点に移動する．
6. JOI 街道の西端から距離 T j の地点に移動し，ツアーを終了する．
ただし，ツアーの経路は JOI 街道を外れないものとする．
理恵さんはこの条件のもと，それぞれの計画についてなるべくツアーの総移動距離を短くしたい．

JOI 街道のアートの情報と理恵さんの計画の情報が与えられたとき，それぞれの計画について，ツアーの総移動距離の最小値を求めるプログラムを作成せよ．

JOIG ツアー– 1 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour

入力
入力は以下の形式で標準入力から与えられる．

N
A1 C1
A2 C2..
.
AN C NQ
S 1 T1S 2 T2..
.
S Q TQ

出力
標準出力に Q 行で出力せよ． j 行目 (1 ≦ j ≦ Q) には，理恵さんの j 番目の計画におけるツアーの総移動距離の最小値を出力せよ．

制約• 4 ≦ N ≦ 100 000．
• 1 ≦ Ai ≦ 1 000 000 000 000 000 (= 1015 ) (1 ≦ i ≦ N)．
• Ai < Ai+1 (1 ≦ i ≦ N − 1)．
• Ci (1 ≦ i ≦ N) は ‘J’，‘O’，‘I’，‘G’ のいずれかである．
• Ci が ‘J’ であるような i (1 ≦ i ≦ N) は 1 つ以上存在する．
• Ci が ‘O’ であるような i (1 ≦ i ≦ N) は 1 つ以上存在する．
• Ci が ‘I’ であるような i (1 ≦ i ≦ N) は 1 つ以上存在する．
• Ci が ‘G’ であるような i (1 ≦ i ≦ N) は 1 つ以上存在する．
• 1 ≦ Q ≦ 100 000．
• 1 ≦ S j ≦ 1 000 000 000 000 000 (= 1015 ) (1 ≦ j ≦ Q)．
• 1 ≦ T j ≦ 1 000 000 000 000 000 (= 1015 ) (1 ≦ j ≦ Q)．
• (S j , T j ) , (S k , T k ) (1 ≦ j < k ≦ Q)．

JOIG ツアー– 2 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
• N, Q は整数である．
• Ai は整数である (1 ≦ i ≦ N)．
• S j , T j は整数である (1 ≦ j ≦ Q)．

小課題
1. (4 点) N ≦ 80，Q ≦ 10．
2. (10 点) N ≦ 500，Q ≦ 10．
3. (6 点) N ≦ 3 000，Q ≦ 100．
4. (25 点) N ≦ 5 000，Q ≦ 1 000．
5. (12 点) Ci が ‘O’ であるような i (1 ≦ i ≦ N)，C j が ‘I’ であるような j (1 ≦ j ≦ N)，Ck が ‘G’ である
ような k (1 ≦ k ≦ N) はそれぞれただ 1 つ存在する．

6. (8 点) Ci が ‘O’ であるような i (1 ≦ i ≦ N) ，C j が ‘I’ であるような j (1 ≦ j ≦ N) はそれぞれただ 1つ存在する．

7. (20 点) Ci が ‘O’ であるような i (1 ≦ i ≦ N) はただ 1 つ存在する．
8. (15 点) 追加の制約はない．

入出力例
入力例 1出力例 177

1 J

122 O
3 G
4 I
5 O
8 G
10 J
23 27 5JOIG ツアー– 3 / 8The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
1 番目の計画は，JOI 街道の西端から距離 3 の地点からツアーを開始し，西端から距離 2 の地点でツアーを終了するというものである．例えば，以下のように移動することで，ツアーの総移動距離を 7 とすることができる．

1. JOI 街道の西端から距離 3 の地点からツアーを開始する．
2. 西に距離 2 だけ移動し，JOI 街道の西端から距離 1 の地点にある ‘J’ と読めるアートを訪れる．
3. 東に距離 1 だけ移動し，JOI 街道の西端から距離 2 の地点にある ‘O’ と読めるアートを訪れる．
4. 東に距離 2 だけ移動し，JOI 街道の西端から距離 4 の地点にある ‘I’ と読めるアートを訪れる．
5. 西に距離 1 だけ移動し，JOI 街道の西端から距離 3 の地点にある ‘G’ と読めるアートを訪れる．
6. 西に距離 1 だけ移動し，JOI 街道の西端から距離 2 の地点でツアーを終了する．
ツアーの総移動距離を 7 未満にすることはできないため，7 を 1 行目に出力する．

2 番目の計画は，JOI 街道の西端から距離 7 の地点からツアーを開始し，西端から距離 5 の地点でツアーを終了するというものである．例えば，以下のように移動することで，ツアーの総移動距離を 12 とすることができる．

1. JOI 街道の西端から距離 7 の地点からツアーを開始する．
2. 東に距離 3 だけ移動し，JOI 街道の西端から距離 10 の地点にある ‘J’ と読めるアートを訪れる．
3. 西に距離 5 だけ移動し，JOI 街道の西端から距離 5 の地点にある ‘O’ と読めるアートを訪れる．
4. 西に距離 1 だけ移動し，JOI 街道の西端から距離 4 の地点にある ‘I’ と読めるアートを訪れる．
5. 西に距離 1 だけ移動し，JOI 街道の西端から距離 3 の地点にある ‘G’ と読めるアートを訪れる．
6. 東に距離 2 だけ移動し，JOI 街道の西端から距離 5 の地点でツアーを終了する．
ツアーの総移動距離を 12 未満にすることはできないため，12 を 2 行目に出力する．
この入力例は小課題 1, 2, 3, 4, 8 の制約を満たす．

JOIG ツアー– 4 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例 2

出力例 21013

5 J

197 O

2010 J

2111 G
12 J
13 I
17 J
18 J
19 J
20 J
44 915 14
6 20
7 20この入力例はすべての小課題の制約を満たす．

JOIG ツアー– 5 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例 3

出力例 3

1025

1 G

27

2 J

28

3 G

174 O

26

7 G

39

9 J

30

10 G
14 I
17 G
19 G
7
11 6
6 3
17 19
1 18
17 17
20 120 10
この入力例は小課題 1, 2, 3, 4, 6, 7, 8 の制約を満たす．

JOIG ツアー– 6 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例 4

出力例 410123 J

175 G

156 I

157 I

198 J

129 I
10 O
14 G
16 I
19 J
64 4
20 3
18 5
15 4
20 1110 8
この入力例は小課題 1, 2, 3, 4, 7, 8 の制約を満たす．

JOIG ツアー– 7 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – JOIG Tour
入力例 5

出力例 5

12583302366935305

179948747891578 I805077987955000

263779425244614 I591304613119987

320153642407146 G

757352272699625

383698990675423 J

478217003098189

478483318441339 J

869691499240121

505589213620811 G

805495866954969

507468309040564 O

1085532869547991

530441288489671 J

928541333618299

730036011088087 O

1205618838253516

896127332008998 I
899298512463927 O
915990785839829 J
10744829561026263 366031656398270
700496830781726 684771674298690
314138534887378 222241904398827
695615197615084 632164325876673
418419052313523 409258287819812
932490604948180 62799105708059
738126150487131 45378717857226
320047965627255 918203067583346
859632377126681 967370566306944
115848334010451 834089404672067
この入力例は小課題 1, 2, 3, 4, 8 の制約を満たす．

JOIG ツアー– 8 / 8