CF2170D.Almost Roman

Let's define a value of a string, consisting of letters "XVI", as follows:

• the value of 'X' is $10$;
• the value of 'V' is $5$;
• the value of 'I' is $1$ or $-1$: $-1$ if the next position contains a letter 'X' or 'V'; $1$ otherwise;
• the value of the entire string is the sum of the values of all letters in it.

You are given a string of characters "XVI?" and asked $q$ queries about it.

In the $i$-th query, three integers are provided:

• $c_X~c_V~c_I$ — the number of available letters 'X', 'V', and 'I', respectively.

What is the minimum value of the string that can be obtained if all question marks are replaced with the letters 'X', 'V', 'I' so that the number of used letters does not exceed the number of available letters of each type?

我们定义由字母“XVI”组成的字符串的值如下：

• 字母 'X' 的值为 $10$；
• 字母 'V' 的值为 $5$；
• 字母 'I' 的值为 $1$ 或 $-1$：若其后一个位置的字符是 'X' 或 'V'，则值为 $-1$；否则为 $1$；
• 整个字符串的值等于其中所有字母的值之和。

给定一个由字符 “XVI?” 组成的字符串，并提出 $q$ 个查询。

在第 $i$ 个查询中，给出三个整数：

• $c_X~c_V~c_I$ —— 分别表示可用的字母 'X'、'V' 和 'I' 的数量。

若将字符串中所有问号 '?' 替换为字母 'X'、'V'、'I'，且每种字母的使用数量不超过其可用数量，则所能得到的字符串的最小可能值是多少？

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$) — the length of the string and the number of queries, respectively.

The second line contains a string consisting of $n$ characters 'X', 'V', 'I' and/or '?'.

The $i$-th of the following $q$ lines contains three integers $c_X, c_V$, and $c_I$ ($0 \le c_X, c_V, c_I \le n$) — the number of available letters 'X', 'V' and 'I' in the $i$-th query.

Additional constraints on the input:

• the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$;
• the sum of $q$ over all test cases does not exceed $3 \cdot 10^5$;
• $c_X + c_V + c_I$ is greater than or equal to the number of '?' characters in the given string.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$）—— 字符串的长度和查询次数。

第二行包含一个由 $n$ 个字符组成的字符串，每个字符为 'X'、'V'、'I' 或 '?'。

接下来的 $q$ 行中，第 $i$ 行包含三个整数 $c_X$、$c_V$ 和 $c_I$（$0 \le c_X, c_V, c_I \le n$）—— 第 $i$ 次查询中可用的字母 'X'、'V' 和 'I' 的数量。

输入的额外约束条件：

• 所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$；
• 所有测试用例的 $q$ 之和不超过 $3 \cdot 10^5$；
• 对于每次查询，均有 $c_X + c_V + c_I \ge$ 给定字符串中 '?' 字符的个数。

For each query, print a single integer — the minimum value of the string that can be obtained by replacing all question marks with the available letters 'X', 'V', and/or 'I'.

对于每个查询，输出一个整数——通过将所有问号替换为可用的字母 'X'、'V' 和/或 'I' 所能得到的字符串的最小值。