Il existe un tableau $a$ composé de $n$ entiers. Initialement, tous les éléments de $a$ sont égaux à 0. Kevin peut effectuer plusieurs opérations sur le tableau. Chaque opération est de l'un des deux types suivants :

• Addition de préfixe — Kevin sélectionne d'abord un indice $x$ ($1 \le x \le n$), puis pour chaque $1 \le j \le x$, il augmente $a_j$ de 1 ;
• Addition de suffixe — Kevin sélectionne d'abord un indice $x$ ($1 \le x \le n$), puis pour chaque $x \le j \le n$, il augmente $a_j$ de 1.

Dans le pays de KDOI, les gens considèrent qu'un entier $v$ est équilibré. Ainsi, Iris donne à Kevin un tableau $c$ composé de $n$ entiers et définit la beauté du tableau $a$ comme suit :

• Initialement, on pose $b = 0$ ;
• Pour chaque $1 \le i \le n$, si $a_i = v$, on ajoute $c_i$ à $b$ ;
• La beauté de $a$ est la valeur finale de $b$.

Kevin veut maximiser la beauté de $a$ après toutes les opérations. Cependant, il avait déjà effectué $m$ opérations alors qu'il était somnolent. Maintenant, il peut effectuer un nombre arbitraire (éventuellement zéro) de nouvelles opérations.

Vous devez aider Kevin à trouver la beauté maximale possible s'il effectue les nouvelles opérations de manière optimale. Cependant, pour s'assurer que vous ne faites pas que lancer les dés, Kevin vous donne un entier $V$, et vous devez résoudre le problème pour chaque $1 \le v \le V$.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un entier unique $t$ ($1 \le t \le 1000$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient trois entiers $n$, $m$ et $V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$) — la longueur du tableau $a$, le nombre d'opérations initiales, et le nombre que Kevin vous donne.

La deuxième ligne contient $n$ entiers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — les éléments du tableau $c$.

Ensuite, $m$ lignes suivent, la $i$-ième ligne contenant un caractère $op$ et un entier $x$ ($op = \text{L}$ ou $\text{R}$, $1 \le x \le n$) — le type de la $i$-ième opération et l'indice sélectionné.

• Si $op = \text{L}$, cette opération est une addition de préfixe sur l'indice $x$ ;
• Si $op = \text{R}$, cette opération est une addition de suffixe sur l'indice $x$.

Il est garanti que :

• la somme de $n$ sur tous les cas de test n'excède pas $2 \cdot 10^5$ ;
• la somme de $m$ sur tous les cas de test n'excède pas $2 \cdot 10^5$ ;
• la somme de $V^2$ sur tous les cas de test n'excède pas $4 \cdot 10^6$.

Sortie

Pour chaque cas de test, affichez $V$ entiers sur une seule ligne, le $i$-ième entier désignant la beauté maximale possible après que Kevin a effectué quelques nouvelles opérations lorsque $v = i$.

Exemples

Entrée 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

Sortie 1

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

Remarque

Dans le premier cas de test, le tableau $a$ change comme suit pour les opérations initiales : $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$.

• Pour $v = 1$, il est optimal de ne pas effectuer de nouvelles opérations, et la beauté est $b = c_2 = 2$ ;
• Pour $v = 2$, il est optimal d'effectuer une opération d'addition de préfixe sur l'indice 2. Après cela, $a$ devient $[3, 2, 2]$, et la beauté est $b = c_2 + c_3 = 6$.

Dans le deuxième cas de test, pour $v = 1$ et $v = 2$, il est optimal de ne pas effectuer de nouvelles opérations.