CFCF2170D.Almost Roman

我们定义一个只包含字母 “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' 替换（要求每种字母的使用次数不超过其可用数量），该字符串可以得到的最小值是多少。

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

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

第二行给出一个长度为 $n$ 的字符串，字符串仅由 'X'、'V'、'I'、'?' 构成。

接下来的 $q$ 行，每行包含三个整数 $c_X,~c_V,~c_I$（$0\leq c_X, c_V, c_I\leq n$）——分别表示本次查询可用的 'X'、'V'、'I' 的个数。

【附加输入约束】

• 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$；
• 所有测试用例中 $q$ 的总和不超过 $3 \times 10^5$；
• 对于每个询问都有 $c_X + c_V + c_I$ 大于等于字符串中问号 '?' 的数量。

对于每个询问，输出一个整数——表示将所有问号替换为可用字母后，字符串可能取得的最小值。