让我们定义一个由字母“组成的字符串值十六”,如下:
- ' 的值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'.
示例
输入复制
43 3???3 0 02 3 10 1 210 7??IV?VXIV?0 0 44 4 01 1 21 1 31 1 41 2 12 2 09 5?V????IVV9 2 44 1 50 1 44 8 13 2 73 2I?V0 1 00 0 1
输出复制
309525433627254253191719331795