G. Сбалансированная задача
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Существует массив $$$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$$$, следует увеличить $$$b$$$ на $$$c_i$$$;
  • Красота массива $$$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, \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$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных массив $$$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$$$ оптимально не выполнять никаких новых операций.