题目背景

星港中有 $n$ 段能量轨道。每段轨道有一个当前能级，初始时所有能级均为 $0$。

工程师可以进行两类注能操作：对某个前缀整体加一，或对某个后缀整体加一。若若干段轨道最终达到了同一个目标能级，就可以共同参与一次星衡校准；第 $i$ 段轨道参与校准会贡献 $c_i$ 点稳定值。

现在已经有一批注能操作被执行。你需要判断在继续进行任意次注能后，对于每个目标能级 $v$，最多能获得多少稳定值。

题目描述

有一个长度为 $n$ 的整数数组 $a$，初始时所有元素均为 $0$。一次操作有以下两种：

• $L\ x$：对所有 $1\le i\le x$，令 $a_i$ 增加 $1$；
• $R\ x$：对所有 $x\le i\le n$，令 $a_i$ 增加 $1$。

题目先给出已经完成的 $m$ 次操作。之后，你还可以继续进行任意次上述操作，也可以不进行新操作。

对于一个给定的整数 $v$，最终数组的稳定值定义为：

你需要对每个 $v=1,2,\dots,V$，分别求出继续操作后能得到的最大稳定值。

输入格式

第一行包含一个整数 $T$，表示测试用例数。

每个测试用例的第一行包含三个整数 $n,m,V$。

第二行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$。

接下来 $m$ 行，每行包含一个字符 $op$ 和一个整数 $x$：

• 若 $op$ 为 $L$，表示一次 $L\ x$ 操作；
• 若 $op$ 为 $R$，表示一次 $R\ x$ 操作。

输出格式

对于每个测试用例，输出一行 $V$ 个整数。第 $v$ 个整数表示目标能级为 $v$ 时的最大稳定值。

样例

输入

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

输出

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

样例解释

在第一组测试数据中，初始操作后数组变为 $[2,1,2]$。

• 当 $v=1$ 时，最优策略是不进行新操作，稳定值为 $c_2=2$；
• 当 $v=2$ 时，可以对下标 $2$ 进行一次前缀加法，数组变为 $[3,2,2]$，稳定值为 $c_2+c_3=6$。

数据范围

对于所有测试数据，满足：

• $1\le T\le 1000$；
• $1\le n,m\le 2\cdot 10^5$；
• $1\le V\le 2000$；
• $1\le c_i\le 10^9$；
• 所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$；
• 所有测试用例的 $m$ 之和不超过 $2\cdot 10^5$；
• 所有测试用例的 $V^2$ 之和不超过 $4\cdot 10^6$。

子任务