Existe un arreglo $a$ que consta de $n$ enteros. Inicialmente, todos los elementos de $a$ son iguales a 0. Kevin puede realizar varias operaciones en el arreglo. Cada operación es de uno de los siguientes dos tipos:

• Adición de prefijo: Kevin selecciona primero un índice $x$ ($1 \le x \le n$), y luego, para cada $1 \le j \le x$, aumenta $a_j$ en 1.
• Adición de sufijo: Kevin selecciona primero un índice $x$ ($1 \le x \le n$), y luego, para cada $x \le j \le n$, aumenta $a_j$ en 1.

En el país de KDOI, la gente piensa que el entero $v$ está equilibrado. Por lo tanto, Iris le da a Kevin un arreglo $c$ que consta de $n$ enteros y define la belleza del arreglo $a$ de la siguiente manera:

• Inicialmente, se establece $b = 0$.
• Para cada $1 \le i \le n$, si $a_i = v$, se suma $c_i$ a $b$.
• La belleza de $a$ es el valor final de $b$.

Kevin quiere maximizar la belleza de $a$ después de todas las operaciones. Sin embargo, ya había realizado $m$ operaciones cuando estaba somnoliento. Ahora, puede realizar un número arbitrario (posiblemente cero) de nuevas operaciones.

Debes ayudar a Kevin a encontrar la máxima belleza posible si realiza las nuevas operaciones de manera óptima. Sin embargo, para asegurarse de que no solo esté lanzando los dados, Kevin te da un entero $V$, y necesitas resolver el problema para cada $1 \le v \le V$.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único entero $t$ ($1 \le t \le 1000$) — el número de casos de prueba. A continuación se describe cada caso de prueba.

La primera línea de cada caso de prueba contiene tres enteros $n$, $m$ y $V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$) — la longitud del arreglo $a$, el número de operaciones iniciales y el número que Kevin te proporciona.

La segunda línea contiene $n$ enteros $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — los elementos del arreglo $c$.

Luego siguen $m$ líneas, donde la $i$-ésima línea contiene un carácter $op$ y un entero $x$ ($op = \text{L}$ o $\text{R}$, $1 \le x \le n$) — el tipo de la $i$-ésima operación y el índice seleccionado.

• Si $op = \text{L}$, esta operación es una adición de prefijo en el índice $x$.
• Si $op = \text{R}$, esta operación es una adición de sufijo en el índice $x$.

Se garantiza que:

• La suma de $n$ sobre todos los casos de prueba no supera $2 \cdot 10^5$.
• La suma de $m$ sobre todos los casos de prueba no supera $2 \cdot 10^5$.
• La suma de $V^2$ sobre todos los casos de prueba no supera $4 \cdot 10^6$.

Salida

Para cada caso de prueba, imprime $V$ enteros en una sola línea, donde el $i$-ésimo entero denota la máxima belleza posible después de que Kevin realice algunas operaciones nuevas cuando $v = i$.

Ejemplos

Entrada 1

5
3 3 2
1 2 4
L 3
R 3
L 1
3 3 2
5 1 4
L 3
R 3
L 1
5 4 5
1 1 1 1 1
L 3
R 2
L 5
L 4
10 12 9
10 9 8 7 6 5 4 3 2 1
L 2
L 4
R 4
R 4
L 6
R 8
L 3
L 2
R 1
R 10
L 8
L 1
1 1 4
1000000000
L 1

Salida 1

2 6
1 9
0 1 3 5 5
0 0 0 6 25 32 35 44 51
1000000000 1000000000 1000000000 1000000000

Nota

En el primer caso de prueba, el arreglo $a$ cambia de la siguiente manera con las operaciones iniciales: $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$.

• Para $v = 1$, es óptimo no realizar ninguna operación nueva, y la belleza es $b = c_2 = 2$.
• Para $v = 2$, es óptimo realizar una operación de adición de prefijo en el índice 2. Después de eso, $a$ se convierte en $[3, 2, 2]$, y la belleza es $b = c_2 + c_3 = 6$.

En el segundo caso de prueba, para ambos $v = 1$ y $v = 2$, es óptimo no realizar ninguna operación nueva.