有一個長度為 $n$ 的陣列 $a$，初始時所有元素皆為 $0$。 Kevin 可以對陣列進行若干次操作。每次操作為以下兩種類型之一：
- 前綴加法 (Prefix addition) — Kevin 先選擇一個索引 $x$ ($1 \le x \le n$)，然後對於每個 $1 \le j \le x$，將 $a_j$ 增加 $1$。
- 後綴加法 (Suffix addition) — Kevin 先選擇一個索引 $x$ ($1 \le x \le n$)，然後對於每個 $x \le j \le n$，將 $a_j$ 增加 $1$。
在 KDOI 國，人們認為整數 $v$ 是平衡的。因此，Iris 給了 Kevin 一個包含 $n$ 個整數的陣列 $c$，並定義陣列 $a$ 的「美感」(beauty) 如下：
- 初始時，設 $b = 0$；
- 對於每個 $1 \le i \le n$，若 $a_i = v$，則將 $c_i$ 加到 $b$；
- 陣列 $a$ 的美感即為 $b$ 的最終值。
Kevin 想要在所有操作完成後最大化 $a$ 的美感。然而，他在昏昏欲睡時已經執行了 $m$ 次操作。現在，他可以執行任意次數（可能為零）的新操作。 你需要幫助 Kevin 在他最佳化執行新操作的情況下，找出可能的最大美感。 為了確保你不是在隨機猜測，Kevin 給了你一個整數 $V$，你需要針對每個 $1 \le v \le V$ 分別求解該問題。
輸入格式
每個測試包含多個測試案例。輸入的第一行包含一個單一整數 $t$ ($1 \le t \le 1000$) — 測試案例的數量。接著是各測試案例的描述。 每個測試案例的第一行包含三個整數 $n, m, V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$) — 陣列 $a$ 的長度、初始操作次數，以及 Kevin 給你的整數。 第二行包含 $n$ 個整數 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — 陣列 $c$ 的元素。 接下來有 $m$ 行，第 $i$ 行包含一個字元 $op$ 和一個整數 $x$ ($op = \text{L}$ 或 $\text{R}$, $1 \le x \le n$) — 第 $i$ 次操作的類型與選擇的索引。
- 若 $op = \text{L}$，此操作為索引 $x$ 的前綴加法；
- 若 $op = \text{R}$，此操作為索引 $x$ 的後綴加法。
保證： 所有測試案例的 $n$ 之和不超過 $2 \cdot 10^5$； 所有測試案例的 $m$ 之和不超過 $2 \cdot 10^5$； * 所有測試案例的 $V^2$ 之和不超過 $4 \cdot 10^6$。
輸出格式
對於每個測試案例，輸出 $V$ 個整數於同一行，第 $i$ 個整數表示當 $v = i$ 時，Kevin 執行某些新操作後可能達到的最大美感。
範例
輸入格式 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
輸出格式 1
2 6 1 9 0 1 3 5 5 0 0 0 6 25 32 35 44 51 1000000000 1000000000 1000000000 1000000000
說明
在第一個測試案例中，陣列 $a$ 經過初始操作後的變化如下： $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$。
- 對於 $v = 1$，最佳策略是不執行任何新操作，美感為 $b = c_2 = 2$；
- 對於 $v = 2$，最佳策略是在索引 $2$ 執行一次前綴加法。之後，$a$ 變為 $[3, 2, 2]$，美感為 $b = c_2 + c_3 = 6$。
在第二個測試案例中，對於 $v = 1$ 和 $v = 2$，最佳策略皆為不執行任何新操作。
備註
在第一個測試案例中，陣列 $a$ 經過初始操作後的變化如下： $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$。
- 對於 $v = 1$，最佳策略是不執行任何新操作，美感為 $b = c_2 = 2$；
- 對於 $v = 2$，最佳策略是在索引 $2$ 執行一次前綴加法。之後，$a$ 變為 $[3, 2, 2]$，美感為 $b = c_2 + c_3 = 6$。
在第二個測試案例中，對於 $v = 1$ 和 $v = 2$，最佳策略皆為不執行任何新操作。