$n$ 個の整数からなる配列 $a$ がある。最初、すべての $a$ の要素は $0$ である。 Kevin は配列に対していくつかの操作を行うことができる。各操作は以下の2種類のいずれかである。
- 接頭辞加算 (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$ ならば $b$ に $c_i$ を加える。
- 配列 $a$ の美しさは、$b$ の最終的な値である。
Kevin はすべての操作が終わった後の $a$ の美しさを最大化したいと考えている。しかし、彼は眠い間にすでに $m$ 回の操作を行ってしまった。今、彼は任意の回数（ゼロ回でもよい）の新しい操作を行うことができる。
Kevin が新しい操作を最適に行った場合に得られる最大の美しさを求める手助けをしてほしい。ただし、単に運任せにならないよう、Kevin は整数 $V$ を与えるので、すべての $1 \le v \le V$ について問題を解く必要がある。
入力
各テストケースは複数のテストケースを含む。入力の最初の行には、テストケースの数を示す単一の整数 $t$ ($1 \le t \le 1000$) が含まれる。続いて各テストケースの説明が続く。
各テストケースの最初の行には、3つの整数 $n, m, V$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le V \le 2000$) が含まれる。これらは配列 $a$ の長さ、初期操作の回数、および Kevin が与える整数 $V$ である。
2行目には、$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$) が含まれる。
- $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$ 個の整数を1行に出力せよ。$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$ となる。
2番目のテストケースでは、$v = 1$ と $v = 2$ の両方において、新しい操作を行わないのが最適である。