Для строки, состоящей из букв «XVI», введем её значение следующим образом:
Дана строка из символов «XVI?», а также $$$q$$$ запросов.
В $$$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' и/или '?'.
В $$$i$$$-й из следующих $$$q$$$ строк записаны три целых числа $$$c_X, c_V$$$ и $$$c_I$$$ ($$$0 \le c_X, c_V, c_I \le n$$$) — количество доступных букв 'X', 'V' и 'I' в $$$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
