AT_joig2023_f タイピング大会 (Typing Contest)

JOIG 国では JOIG 語が使用されており，JOIG 語では文字 `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H`, `I`, `J`, `K`, `L`, `M`, `N`, `O` の $ 15 $ 種類の文字が用いられる． 来月 JOIG 国で開催されるタイピング大会では，JOIG 語で用いられる $ 15 $ 種類の文字からなる長さ $ N $ の文字列 $ S $ を入力するのにかかる時間を競う．この大会では，参加者は以下の条件でタイピングを行う． - 参加者は， $ 1 $ 本の指を使ってタイピングをする． - 参加者は， $ 15 $ 種類の文字のキー $ 1 $ つずつを $ 1 $ 列に並べた，左右に細長いキーボードを使用する．なお，どの位置にどの文字のキーを配置するかは，各参加者が自由に決めることができる． - 参加者は，文字列 $ S $ の $ 1, 2, \dots, N $ 文字目のキーをこの順に打つことによって文字列 $ S $ を入力する． この大会には $ Q $ 人が参加する予定である．参加者によってタイピングの能力は様々である． $ i $ 番目 ( $ 1 \leqq i \leqq Q $ ) の参加者は，タイピングに際して以下のような時間がかかる． - 指の真下にあるキーを $ 1 $ 回打つのに $ A_i $ ミリ秒かかる． - 指を $ 1 $ つ左のキーの上に移動させるのに $ L_i $ ミリ秒かかる． - 指を $ 1 $ つ右のキーの上に移動させるのに $ R_i $ ミリ秒かかる． 文字列 $ S $ および各参加者の情報が与えられるので，各参加者に対して，文字列 $ S $ の最初の文字を打ち始めてから最後の文字を打ち終わるまでに最短何ミリ秒かかるかを求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ S $ $ Q $ $ A_1 $ $ L_1 $ $ R_1 $ $ A_2 $ $ L_2 $ $ R_2 $ $ \vdots $ $ A_Q $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ． $ i $ 行目 ( $ 1 \leqq i \leqq Q $ ) には，参加者 $ i $ が文字列 $ S $ の最初の文字を打ち始めてから最後の文字を打ち終わるまでに最短何ミリ秒かかるかを出力せよ．

### 小課題 1. ( $ 2 $ 点) $ S $ の各文字は `A` である， $ Q = 1 $ ． 2. ( $ 3 $ 点) $ S $ の各文字は `A`, `B` のいずれかである， $ Q = 1 $ ． 3. ( $ 4 $ 点) $ S $ の各文字は `A`, `B`, `C` のいずれかである， $ Q = 1 $ ． 4. ( $ 9 $ 点) $ S $ の各文字は `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H` のいずれかである， $ Q = 1 $ ， $ N \leqq 100 $ ． 5. ( $ 14 $ 点) $ S $ の各文字は `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H` のいずれかである， $ Q = 1 $ ． 6. ( $ 26 $ 点) $ S $ の各文字は `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H` のいずれかである． 7. ( $ 23 $ 点) $ Q = 1 $ ． 8. ( $ 7 $ 点) $ L_i = R_i $ ( $ 1 \leqq i \leqq Q $ )． 9. ( $ 12 $ 点) 追加の制約はない． ### Sample Explanation 1 例えば，キーボードの配列を左から順に `ONMLKJIHGFEDCBA` とすることを考える．このとき，以下の表のような動作を行うことで， $ 1\,110 $ ミリ秒で文字列 `ABAABB` を入力できる． 手順 動作 指の真下にあるキー 時間（ミリ秒） 1 A のキーを打つ A 100 2 指を $ 1 $ つ左のキーの上に移動させる A → B 150 3 B のキーを打つ B 100 4 指を $ 1 $ つ右のキーの上に移動させる B → A 210 5 A のキーを打つ A 100 6 A のキーを打つ A 100 7 指を $ 1 $ つ左のキーの上に移動させる A → B 150 8 B のキーを打つ B 100 9 B のキーを打つ B 100 上に挙げたキーボードの配列以外にも，文字列 `ABAABB` を同じ時間で入力できるものはあるが，より短い時間で入力することはできない．よって $ 1\,110 $ を出力する． この入力例は小課題 $ 2, 3, 4, 5, 6, 7, 9 $ の制約を満たす． ### Sample Explanation 2 例えば，キーボードの配列を左から順に `CABDEFGHIJKLMNO` とすることを考える．このとき，以下の表のような動作を行うことで， $ 2\,260 $ ミリ秒で文字列 `CBACAB` を入力できる． 手順 動作 指の真下にあるキー 時間（ミリ秒） 1 C のキーを打つ C 150 2 指を $ 1 $ つ右のキーの上に移動させる C → A 220 3 指を $ 1 $ つ右のキーの上に移動させる A → B 220 4 B のキーを打つ B 150 5 指を $ 1 $ つ左のキーの上に移動させる B → A 240 6 A のキーを打つ A 150 7 指を $ 1 $ つ左のキーの上に移動させる A → C 240 8 C のキーを打つ C 150 9 指を $ 1 $ つ右のキーの上に移動させる C → A 220 10 A のキーを打つ A 150 11 指を $ 1 $ つ右のキーの上に移動させる A → B 220 12 B のキーを打つ B 150 上に挙げたキーボードの配列以外でも，文字列 `CBACAB` を同じ時間で入力できるものはあるが，より短い時間で入力することはできない．よって $ 2\,260 $ を出力する． この入力例は小課題 $ 3, 4, 5, 6, 7, 9 $ の制約を満たす． ### Sample Explanation 3 `A` を $ 20 $ 回打つことになるので，キーボードの配列にかかわらず，入力し終わるまでに最短で $ 230\,000\,000 \times 20 = 4\,600\,000\,000 $ ミリ秒かかる．よって $ 4\,600\,000\,000 $ を出力する． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 6, 9 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 8, 9 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 1\,000\,000 $ ． - $ S $ は長さ $ N $ の文字列である． - $ S $ の各文字は `A`, `B`, `C`, `D`, `E`, `F`, `G`, `H`, `I`, `J`, `K`, `L`, `M`, `N`, `O` のいずれかである． - $ 1 \leqq Q \leqq 150\,000 $ ． - $ 1 \leqq A_i \leqq 10^{11} $ ( $ 1 \leqq i \leqq Q $ )． - $ 1 \leqq L_i \leqq 10^{11} $ ( $ 1 \leqq i \leqq Q $ )． - $ 1 \leqq R_i \leqq 10^{11} $ ( $ 1 \leqq i \leqq Q $ )． - $ N, Q, A_i, L_i, R_i $ は整数である．