D. Ряд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд вдоль одной линии стоят $$$n$$$ человек, каждый смотрит либо влево, либо вправо.

Каждый человек посчитал количество людей, которое он видит (то есть количество человек в направлении его взгляда). Назовём величиной ряда сумму посчитанных значений.

Например, если люди стоят следующим образом: LRRLL, где L обозначает человека в направлении «влево», а R обозначает человека в направлении «вправо», то посчитанные значения равны $$$[0, 3, 2, 3, 4]$$$, а величина ряда равна $$$0+3+2+3+4=12$$$.

Вам задано начальное расположение людей вдоль линии. Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$, определите максимальную возможную величину ряда, если вы можете изменить направление не более чем у $$$k$$$ человек.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — количество человек в ряду.

Следующая строка состоит из $$$n$$$ символов, каждый из которых либо L, либо R — строка описывает направления для всех людей.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

Обратите внимание, что ответ для некоторых наборов входных данных может не поместиться в 32-битный тип данных, поэтому вы должны использовать 64-битный тип данных из вашего языка программирования (например, long long в C++).

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — для всех $$$k$$$ от $$$1$$$ до $$$n$$$ выведите максимальное значение ряда, если можно изменить направление не более чем $$$k$$$ человек в ряду.

Пример
Входные данные
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL
Выходные данные
3 5 5 
16 16 16 16 16 
0 
86 95 98 101 102 102 102 102 102 102 102 102 
29 38 45 52 57 62 65 68 69 70 
44 50 54 56 56 56 56 56 56
Примечание

В первом наборе входных данных примера:

  • $$$k=1$$$: изменим направление $$$1$$$-го человека, чтобы достичь состояния RLR. В этом случае величина ряда равна $$$2+1+0=3$$$.
  • $$$k=2$$$: изменим направление $$$2$$$-х человек, чтобы ряд принял вид RLL. В этом случае величина ряда будет равна $$$2+1+2=5$$$.
  • $$$k=3$$$: изменим направление $$$2$$$-х человек, чтобы ряд принял вид RLL. В этом случае величина ряда будет равна $$$2+1+2=5$$$ (обратите внимание, что можно менять направление $$$k$$$ или меньше людей).

Во втором наборе входных данных примера для каждого $$$k$$$ от $$$1$$$ до $$$5$$$ достаточно только лишь менять направление одного первого человека (чтобы ряд принял вид RRRLL).