← 返回题目列表

Codeforces · 2170/D

D. 几乎罗马

中文机器翻译题面 查看原题

让我们定义一个由字母“组成的字符串值十六”,如下:

  • ' 的值X' 是 $$$10$$$;
  • ' 的值V' 是 $$$5$$$;
  • ' 的值I' 是 $$$1$$$ 或 $$$-1$$$: $$$-1$$$ 如果下一个位置包含字母 'X' 或 'V'; $$$1$$$ 否则;
  • 整个字符串的值是其中所有字母的值之和。

给你一串字符“十六?”并询问了$$$q$$$对此的疑问。

在第 $$$i$$$ 查询中,提供了三个整数:

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

将所有问号替换为字母 ' 可以得到的字符串最小值是多少X', 'V', 'I'以便使用的字母数量不超过每种类型的可用字母数量?

输入

第一行包含一个整数 $$$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$$$) - 可用字母的数量 'X', 'V' 和 'I' 在第 $$$i$$$ 查询中。

输入的附加限制:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$;
  • 所有测试用例的 $$$q$$$ 总和不超过 $$$3 \cdot 10^5$$$;
  • $$$c_X + c_V + c_I$$$ 大于或等于 ' 的数量?' 给定字符串中的字符。

输出

对于每个查询,打印一个整数 - 通过将所有问号替换为可用字母 ' 可以获得的字符串的最小值X', 'V', 和/或 'I'.

示例

输入
复制

4
3 3
???
3 0 0
2 3 1
0 1 2
10 7
??IV?VXIV?
0 0 4
4 4 0
1 1 2
1 1 3
1 1 4
1 2 1
2 2 0
9 5
?V????IVV
9 2 4
4 1 5
0 1 4
4 8 1
3 2 7
3 2
I?V
0 1 0
0 0 1

输出
复制

30
9
5
25
43
36
27
25
42
53
19
17
19
33
17
9
5