Mamy tablicę $a$ składającą się z $n$ liczb całkowitych. Początkowo wszystkie elementy $a$ są równe 0. Kevin może wykonywać na tablicy różne operacje. Każda operacja jest jednego z dwóch następujących typów:

• Dodawanie prefiksowe — Kevin wybiera indeks $x$ ($1 \le x \le n$), a następnie dla każdego $1 \le j \le x$ zwiększa $a_j$ o 1.
• Dodawanie sufiksowe — Kevin wybiera indeks $x$ ($1 \le x \le n$), a następnie dla każdego $x \le j \le n$ zwiększa $a_j$ o 1.

W kraju KDOI uważa się, że liczba całkowita $v$ jest zrównoważona. Iris daje Kevinowi tablicę $c$ składającą się z $n$ liczb całkowitych i definiuje piękno tablicy $a$ w następujący sposób:

• Początkowo ustawiamy $b = 0$.
• Dla każdego $1 \le i \le n$, jeśli $a_i = v$, dodajemy $c_i$ do $b$.
• Piękno tablicy $a$ to końcowa wartość $b$.

Kevin chce zmaksymalizować piękno tablicy $a$ po wykonaniu wszystkich operacji. Wykonał on już jednak $m$ operacji, gdy był śpiący. Teraz może wykonać dowolną liczbę (być może zero) nowych operacji. Musisz pomóc Kevinowi znaleźć maksymalne możliwe piękno, jeśli optymalnie wykona nowe operacje. Aby upewnić się, że nie zgadujesz, Kevin podaje Ci liczbę całkowitą $V$ i musisz rozwiązać problem dla każdego $1 \le v \le V$.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 1000$) — liczbę przypadków testowych. Następnie następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera trzy liczby całkowite $n, m$ oraz $V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$) — długość tablicy $a$, liczbę początkowych operacji oraz liczbę podaną przez Kevina.

Druga linia zawiera $n$ liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — elementy tablicy $c$.

Następnie następuje $m$ linii, z których $i$-ta linia zawiera znak $op$ oraz liczbę całkowitą $x$ ($op = \text{L}$ lub $\text{R}$, $1 \le x \le n$) — typ $i$-tej operacji oraz wybrany indeks.

• Jeśli $op = \text{L}$, operacja ta jest dodawaniem prefiksowym na indeksie $x$.
• Jeśli $op = \text{R}$, operacja ta jest dodawaniem sufiksowym na indeksie $x$.

Gwarantuje się, że:

• suma $n$ we wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$;
• suma $m$ we wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$;
• suma $V^2$ we wszystkich przypadkach testowych nie przekracza $4 \cdot 10^6$.

Wyjście

Dla każdego przypadku testowego wypisz $V$ liczb całkowitych w jednej linii, gdzie $i$-ta liczba oznacza maksymalne możliwe piękno po wykonaniu przez Kevina pewnych nowych operacji dla $v = i$.

Przykład

Wejście 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

Wyjście 1

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

Uwagi

W pierwszym przypadku testowym tablica $a$ zmienia się w wyniku początkowych operacji następująco: $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$.

• Dla $v = 1$ optymalnie jest nie wykonywać żadnych nowych operacji, a piękno wynosi $b = c_2 = 2$.
• Dla $v = 2$ optymalnie jest wykonać operację dodawania prefiksowego na indeksie 2. Po tym tablica $a$ staje się $[3, 2, 2]$, a piękno wynosi $b = c_2 + c_3 = 6$.

W drugim przypadku testowym, zarówno dla $v = 1$, jak i $v = 2$, optymalnie jest nie wykonywać żadnych nowych operacji.