There is an array (a) consisting of (n) integers. Initially, all elements of (a) are equal to (0). Kevin can perform several operations on the array. Each operation is one of the following two types: Prefix addition — Kevin first selects an index (x) ((1\le x\le n)), and then for each (1\le j\le x), increases (a_j) by (1); Suffix addition — Kevin first selects an index (x) ((1\le x\le n)), and then for each (x\le j\le n), increases (a_j) by (1). In the country of KDOI, people think that the integer (v) is balanced. Thus, Iris gives Kevin an array (c) consisting of (n) integers and defines the beauty of the array (a) as follows: Initially, set (b=0); For each (1\le i\le n), if (a_i=v), add (c_i) to (b); The beauty of (a) is the final value of (b). Kevin wants to maximize the beauty of (a) after all the operations. However, he had already performed (m) operations when he was sleepy. Now, he can perform an arbitrary number (possibly zero) of new operations. You have to help Kevin find the maximum possible beauty if he optimally performs the new operations. However, to make sure that you are not just rolling the dice, Kevin gives you an integer (V), and you need to solve the problem for each (1\le v\le V). Each test contains multiple test cases. The first line of the input contains a single integer (t) ((1\le t\le 1000)) — the number of test cases. The description of test cases follows. The first line of each test case contains three integers (n), (m), and (V) ((1\le n, m\le 2\cdot 10^5), (1\le V\le 2000)) — the length of the array (a), the number of initial operations, and the number that Kevin gives you. The second line contains (n) integers (c_1, c_2, \ldots, c_n) ((1\le c_i\le 10^9)) — the elements in the array (c). Then (m) lines follow, the (i)-th line containing a character (op) a