有一个长度为 $n$ 的数组 $a$，初始时 $a$ 的所有元素均为 $0$。 Kevin 可以对数组执行若干操作。每次操作属于以下两种类型之一： 前缀加：Kevin 首先选择一个下标 $x$ ($1 \le x \le n$)，然后对于每个 $1 \le j \le x$，将 $a_j$ 增加 $1$； 后缀加：Kevin 首先选择一个下标 $x$ ($1 \le x \le n$)，然后对于每个 $x \le j \le n$，将 $a_j$ 增加 $1$。

在 KDOI 国，人们认为整数 $v$ 是平衡的。因此，Iris 给 Kevin 一个包含 $n$ 个整数的数组 $c$，并定义数组 $a$ 的“美观度”如下： 初始时，设 $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 给出的整数 $V$。 第二行包含 $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$，最优策略均是不执行任何新操作。