타이핑 대회

JOIG 국에서는 JOIG 어를 사용하며, JOIG 어에는 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 15종류의 문자가 쓰인다.

다음 달 JOIG 국에서 열리는 타이핑 대회에서는 이 15종류의 문자로 이루어진 길이 $N$의 문자열 $S$를 입력하는 데 걸리는 시간을 겨룬다. 참가자는 다음 조건에 따라 타이핑한다.

• 참가자는 손가락 1개로 타이핑한다.
• 참가자는 15종류의 문자 키를 각각 하나씩 한 줄로 늘어놓은, 좌우로 긴 키보드를 사용한다. 각 문자 키를 어느 위치에 배치할지는 참가자가 자유롭게 정한다.
• 참가자는 $S$의 1번째, 2번째, …, $N$번째 문자의 키를 이 순서대로 눌러 $S$를 입력한다.

이 대회에는 $Q$명이 참가한다. 참가자마다 타이핑 능력이 다르다. $i$번째 ($1 \leq i \leq Q$) 참가자의 소요 시간은 다음과 같다.

• 손가락 바로 밑에 있는 키를 한 번 누르는 데 $A_i$밀리초가 걸린다.
• 손가락을 왼쪽 키 위로 한 칸 옮기는 데 $L_i$밀리초가 걸린다.
• 손가락을 오른쪽 키 위로 한 칸 옮기는 데 $R_i$밀리초가 걸린다.

문자열 $S$와 각 참가자의 정보가 주어진다. 각 참가자에 대해 $S$의 첫 문자를 누르기 시작해서 마지막 문자를 누르고 마칠 때까지 걸리는 최소 시간을 밀리초 단위로 구하라.

N
S
Q
A1 L1 R1
:
AQ LQ RQ

$Q$개의 줄을 출력한다. $i$번째 줄 ($1 \leq i \leq Q$)에는 $i$번째 참가자가 $S$의 첫 문자를 누르기 시작해서 마지막 문자를 누르고 마칠 때까지 걸리는 최소 시간을 밀리초 단위로 출력한다.

• $1 \leq N \leq 1000000$
• $S$는 길이 $N$의 문자열이다.
• $S$의 각 문자는 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 중 하나이다.
• $1 \leq Q \leq 150000$
• $1 \leq A_i \leq 10^{11}$ ($1 \leq i \leq Q$)
• $1 \leq L_i \leq 10^{11}$ ($1 \leq i \leq Q$)
• $1 \leq R_i \leq 10^{11}$ ($1 \leq i \leq Q$)
• $N$, $Q$, $A_i$, $L_i$, $R_i$는 정수이다.