27546번 - タイピング大会 (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, …, N 文字目のキーをこの順に打つことによって文字列 S を入力する．

この大会には Q 人が参加する予定である．参加者によってタイピングの能力は様々である．i 番目 (1 ≦ i ≦ Q) の参加者は，タイピングに際して以下のような時間がかかる．

• 指の真下にあるキーを 1 回打つのに A_i ミリ秒かかる．
• 指を 1 つ左のキーの上に移動させるのに L_i ミリ秒かかる．
• 指を 1 つ右のキーの上に移動させるのに R_i ミリ秒かかる．

文字列 S および各参加者の情報が与えられるので，各参加者に対して，文字列 S の最初の文字を打ち始めてから最後の文字を打ち終わるまでに最短何ミリ秒かかるかを求めるプログラムを作成せよ．

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

N
S
Q
A1 L1 R1
A2 L2 R2
:
AQ LQ RQ

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

• 1 ≦ N ≦ 1 000 000．
• S は長さ N の文字列である．
• S の各文字は A, B, C, D, E, F, G, H, I, J, K, L, M, N, O のいずれかである．
• 1 ≦ Q ≦ 150 000．
• 1 ≦ A_i ≦ 10¹¹ (1 ≦ i ≦ Q)．
• 1 ≦ L_i ≦ 10¹¹ (1 ≦ i ≦ Q)．
• 1 ≦ R_i ≦ 10¹¹ (1 ≦ i ≦ Q)．
• N, Q, A_i, L_i, R_i は整数である．