有一个数组 $$$a$$$ 由 $$$n$$$ 整数组成。最初,$$$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 给了你一个整数 $$$V$$$,你需要解决每个 $$$1\le v\le V$$$ 的问题。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1\let 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, \ldots, c_n$$$ ($$$1\le c_i\le 10^9$$$) — 数组 $$$c$$$ 中的元素。
接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含字符 $$$op$$$ 和整数 $$$x$$$ ($$$op=\mathtt{L}$$$ 或 $$$\mathtt{R}$$$, $$$1\le x\le n$$$) - 第 $$$i$$$ 操作的类型和选定的索引。
- 如果$$$op=\mathtt{L}$$$,则此操作是索引$$$x$$$上的前缀加法;
- 如果 $$$op=\mathtt{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{\mathtt{L}\ 3} [1, 1, 1] \xrightarrow{\mathtt{R}\ 3} [1, 1, 2] \xrightarrow{\mathtt{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$$$ 来说,最好不执行任何新操作。