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? 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. 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 '.