Typing Contest

Time limit2.5sMemory limit1024 MB

Summary

Given a 15-letter string and each contestant's press, left, and right costs, find the minimum typing time when the keys can be placed in any order on one row.

Level: Hard9 of 10
Topics: Dynamic programming, Bit manipulation, Geometry
Solved: No attempts yet

Problem

In the JOIG country, the JOIG language is used. It has 15 letters: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O.

At a typing contest held in the JOIG country next month, contestants compete on how long it takes to enter a string $S$ of length $N$ made of these 15 letters. Each contestant types under the following rules.

A contestant types with one finger.
The contestant uses a long, narrow keyboard where each of the 15 letter keys appears once in a single row. The contestant may choose the position of each letter key freely.
The contestant enters $S$ by pressing the keys for the 1st, 2nd, ..., $N$ th characters of $S$ , in that order.

Q contestants will take part. Each contestant has a different typing ability. For the $i$ th contestant ( $1 \leq i \leq Q$ ), the times are as follows.

Pressing the key directly under the finger takes $A_i$ milliseconds.
Moving the finger one key to the left takes $L_i$ milliseconds.
Moving the finger one key to the right takes $R_i$ milliseconds.

You are given the string $S$ and the information for each contestant. For each contestant, find the shortest possible time in milliseconds from pressing the first character of $S$ to finishing the last character.

Input

N
S
Q
A1 L1 R1
:
AQ LQ RQ

Output

Print $Q$ lines. On line $i$ ( $1 \leq i \leq Q$ ), print the shortest time in milliseconds for contestant $i$ to type $S$ , from pressing its first character to finishing its last character.

Constraints

$1 \leq N \leq 1000000$ .
$S$ is a string of length $N$ .
Each character of $S$ is one of 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$ , and $R_i$ are integers.

Examples5

Example 1
Input
```
6
ABAABB
1
100 150 210
```
Expected output
```
1110
```
Example 2
Input
```
6
CBACAB
1
150 240 220
```
Expected output
```
2260
```

Example 3

Input

20
AAAAAAAAAAAAAAAAAAAA
1
230000000 80000000 80000000

Expected output

4600000000

Example 4

Input

7
EACHBAG
5
130 104 162
107 219 45
144 168 157
213 79 257
100000000000 100000000000 100000000000

Expected output

2078
1766
2465
2894
1600000000000

Example 5

Input

19
JOIGCODINGCHALLENGE
5
1 1 1
100 200 200
225 111 111
123456789 987654321 987654321
31415926535 27182818284 27182818284

Expected output

48
7700
7494
30987654300
1385204334401