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:
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:
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$$$ and an integer $$$x$$$ ($$$op=\mathtt{L}$$$ or $$$\mathtt{R}$$$, $$$1\le x\le n$$$) — the type of the $$$i$$$-th operation and the selected index.
It is guaranteed that:
For each test case, output $$$V$$$ integers in a single line, the $$$i$$$-th integer denoting the maximum possible beauty after Kevin performs some new operations when $$$v=i$$$.
53 3 21 2 4L 3R 3L 13 3 25 1 4L 3R 3L 15 4 51 1 1 1 1L 3R 2L 5L 410 12 910 9 8 7 6 5 4 3 2 1L 2L 4R 4R 4L 6R 8L 3L 2R 1R 10L 8L 11 1 41000000000L 1
2 6 1 9 0 1 3 5 5 0 0 0 6 25 32 35 44 51 1000000000 1000000000 1000000000 1000000000
In the first test case, the array $$$a$$$ changes as follows for the initial operations: $$$[0, 0, 0] \xrightarrow{\mathtt{L}\ 3} [1, 1, 1] \xrightarrow{\mathtt{R}\ 3} [1, 1, 2] \xrightarrow{\mathtt{L}\ 1} [2, 1, 2]$$$.
In the second test case, for both $$$v=1$$$ and $$$v=2$$$, it is optimal to not perform any new operations.
Name |
---|