D. Almost Roman
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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?

Input

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.
Output

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

Example
Input
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
Output
30
9
5
25
43
36
27
25
42
53
19
17
19
33
17
9
5