Имеется массив $a$, состоящий из $n$ целых чисел. Изначально все элементы $a$ равны 0. Кевин может выполнять несколько операций над массивом. Каждая операция относится к одному из двух следующих типов: Прибавление к префиксу — Кевин выбирает индекс $x$ ($1 \le x \le n$), а затем для каждого $1 \le j \le x$ увеличивает $a_j$ на 1. Прибавление к суффиксу — Кевин выбирает индекс $x$ ($1 \le x \le n$), а затем для каждого $x \le j \le n$ увеличивает $a_j$ на 1.
В стране KDOI считается, что целое число $v$ является сбалансированным. Айрис дает Кевину массив $c$, состоящий из $n$ целых чисел, и определяет красоту массива $a$ следующим образом: Изначально установим $b = 0$. Для каждого $1 \le i \le n$, если $a_i = v$, прибавим $c_i$ к $b$. * Красота $a$ — это итоговое значение $b$.
Кевин хочет максимизировать красоту $a$ после всех операций. Однако он уже выполнил $m$ операций, пока был сонный. Теперь он может выполнить произвольное количество (возможно, ноль) новых операций. Вам нужно помочь Кевину найти максимально возможную красоту, если он оптимально выполнит новые операции. Однако, чтобы убедиться, что вы не просто угадываете, Кевин дает вам целое число $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$, количество начальных операций и число, которое дает вам Кевин. Вторая строка содержит $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$.
Примеры
Входные данные 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$ оптимально не выполнять никаких новых операций.