在 JOIG 国家，人们使用 JOIG 语言。在 JOIG 语言中，共有 $15$ 种字符：A, B, C, D, E, F, G, H, I, J, K, L, M, N, O。

下个月将在 JOIG 国举行一次打字比赛，比拼使用 $15$ 种字符组成的长度为 $N$ 的字符串 $S$ 的输入所需时间。在本次比赛中，参赛者需遵循以下规则进行打字：

• 参赛者只能用一根手指进行打字。
• 参赛者需使用一排按键呈一行排布、极为狭长的键盘，$15$ 个字符的键依次排在键盘上。每位参赛者可以自由决定各字符按键的具体排列顺序与位置。
• 参赛者需依次输入字符串 $S$ 的第 $1, 2, \dots, N$ 个字符。

本次比赛共有 $Q$ 位参赛者。不同参赛者的打字能力不同。第 $i$ 位参赛者（$1 \leq i \leq Q$）的打字规则如下：

• 按下手指正下方的按键一次需要 $A_i$ 毫秒。
• 手指每向左移动一个按键需 $L_i$ 毫秒。
• 手指每向右移动一个按键需 $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 \leq i \leq 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 \leq 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 \leq i \leq Q$）。
9.（$12$ 分）无其他额外限制。

样例说明 1

例如，考虑键盘从左到右依次排列为 ONMLKJIHGFEDCBA。此时，按照下表的操作，输入字符串 ABAABB 总共需要 $1\,110$ 毫秒。

步骤	操作	指下按键	用时（毫秒）
1	按下 A	A	100
2	向左移一位至 B	A → B	150
3	按下 B	B	100
4	向右移一位至 A	B → A	210
5	按下 A	A	100
6	按下 A	A	100
7	向左移一位至 B	A → B	150
8	按下 B	B	100
9	按下 B	B	100

除了上述键盘排列外，也可能有其它能在 $1\,110$ 毫秒内完成输入的布局，但无法更快。因此，输出 $1\,110$。

此输入数据满足子任务 $2, 3, 4, 5, 6, 7, 9$ 的限制。

样例说明 2

例如，考虑键盘从左到右依次排列为 CABDEFGHIJKLMNO。此时，按照下表的操作，输入字符串 CBACAB 总共需要 $2\,260$ 毫秒。

步骤	操作	指下按键	用时（毫秒）
1	按下 C	C	150
2	向右移一位至 A	C → A	220
3	向右移一位至 B	A → B	220
4	按下 B	B	150
5	向左移一位至 A	B → A	240
6	按下 A	A	150
7	向左移一位至 C	A → C	240
8	按下 C	C	150
9	向右移一位至 A	C → A	220
10	按下 A	A	150
11	向右移一位至 B	A → B	220
12	按下 B	B	150

除了上述键盘排列外，也可能有其它能在 $2\,260$ 毫秒内完成输入的布局，但无法更快。因此，输出 $2\,260$。

此输入数据满足子任务 $3, 4, 5, 6, 7, 9$ 的限制。

样例说明 3

由于需要连续输入 $20$ 次 A，无论键位如何排列，总时间为 $230\,000\,000 \times 20 = 4\,600\,000\,000$ 毫秒。因此，应输出 $4\,600\,000\,000$。

该输入数据满足所有子任务的限制。

样例说明 4

本样例满足子任务 $6, 9$ 的限制。

样例说明 5

本样例满足子任务 $8, 9$ 的限制。

数据范围与约定

• $1 \leq N \leq 1\,000\,000$。
• $S$ 是长度为 $N$ 的字符串。
• $S$ 的每个字符为 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 之一。
• $1 \leq Q \leq 150\,000$。
• $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$ 均为整数。

由 ChatGPT 5 翻译