There are $n$ people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count.

For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are $[0, 3, 2, 3, 4]$, and the value is $0+3+2+3+4=12$.

You are given the initial arrangement of people in the line. For each $k$ from $1$ to $n$, determine the maximum value of the line if you can change the direction of at most $k$ people.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the line.

The following line contains a string consisting of $n$ characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).


-----Output-----

For each test case, output $n$ space-separated non-negative integers — the maximum value of the line if you can change the direction of at most $k$ people for each $k$ from $1$ to $n$, inclusive.


-----Examples-----

Input
6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL
Output
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


-----Note-----

In the first test case:

$k=1$: change the direction of $1$ person to make the line RLR. The total value is $2+1+0=3$.

$k=2$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$.

$k=3$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$. Note that you have to change the direction of at most $k$ people.

In the second test case, it is optimal to only change the direction of the first person for all $k$ from $1$ to $5$ (that is, make the line RRRLL).

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
import sys

def run():
	n = int(input())
	line = sys.stdin.readline().strip()
	count = len(line) - 1
	value = 0
	for i in range(len(line)):
		if line[i] == 'L':
			value += i
		if line[i] == 'R':
			value += count - i
	values = []
	l = 0
	r = len(line) - 1
	while l < r:
		if line[l] == 'L':
			value -= l
			value += count - l
			values.append(value)
		if line[r] == 'R':
			value += r
			value -= count - r
			values.append(value)
		l += 1
		r -= 1
	values.extend([value for _ in range(n - len(values))])
	print(' '.join((str(x) for x in values)))
t = int(input())
for _ in range(t):
	run()


def line_score(s_len, s):
	biggest_change_earn = []
	for (i, direction) in enumerate(s):
		(left, right) = (i, s_len - i - 1)
		if direction == 'L':
			biggest_change_earn.append(right - left)
		else:
			biggest_change_earn.append(left - right)
	biggest_change_earn.sort()
	curr_score = 0
	for (i, direction) in enumerate(s):
		if direction == 'L':
			curr_score += i
		else:
			curr_score += s_len - i - 1
	scores = []
	while biggest_change_earn and biggest_change_earn[-1] > 0:
		curr_score += biggest_change_earn.pop()
		scores.append(curr_score)
	scores.extend([curr_score] * len(biggest_change_earn))
	return scores
num_test_cases = int(input())
for test_case in range(num_test_cases):
	s_len = int(input())
	s = input()
	print(' '.join(list(map(str, line_score(s_len, s)))))


t = int(input())

def solve(n, dirs):
	counts = []
	m = n - 1
	for i in range(n):
		if dirs[i] == 'L':
			counts.append(i)
		else:
			counts.append(m - i)
	counts.sort()
	k = sum(counts)
	opts = []
	for i in range(n):
		u = counts[i]
		v = m - u
		if v > u:
			k -= u
			k += v
		opts.append(str(k))
	print(' '.join(opts))
for i in range(t):
	n = int(input())
	dirs = input()
	solve(n, dirs)


def solve():
	k = int(input())
	a = input()
	sum_a = 0
	n = len(a)
	for i in range(n):
		if a[i] == 'R':
			sum_a += n - i - 1
		else:
			sum_a += i
	s = []
	for i in range(n // 2 + 1):
		if i == n // 2 and n % 2 == 1:
			r = a[i]
			if r == 'L':
				o = sum_a - i + (n - i - 1)
				sum_a = max(sum_a, o)
				s.append(sum_a)
		else:
			r = a[i]
			l = a[-(i + 1)]
			if r == 'L':
				o = sum_a - i + (n - i - 1)
				sum_a = max(sum_a, o)
				s.append(sum_a)
			if l == 'R':
				o = sum_a - i + (n - i - 1)
				sum_a = max(sum_a, o)
				s.append(sum_a)
	s += [sum_a] * (n - len(s))
	return ' '.join([str(i) for i in s])
t = int(input())
ans = []
while t:
	ans.append(solve())
	t -= 1
print('\n'.join(ans))


import math

def solve():
	k = int(input())
	s = list(input())
	n = len(s)
	val = 0
	for i in range(len(s)):
		if s[i] == 'L':
			val += i
		else:
			val += n - 1 - i
	l = 0
	h = n - 1
	ans = []
	while k > 0 and l < h:
		if s[l] == 'L' and l <= n // 2:
			k -= 1
			val += n - 1 - 2 * l
			l += 1
			ans.append(val)
		else:
			l += 1
		if k < 0:
			break
		if s[h] == 'R' and h >= n // 2:
			k -= 1
			val += 2 * h - n + 1
			ans.append(val)
			h -= 1
		else:
			h -= 1
	while k > 0:
		ans.append(val)
		k -= 1
	print(' '.join(map(str, ans)))
t = int(input())
while t > 0:
	solve()
	t -= 1


def solve(n, s):
	value = []
	origional = 0
	for (i, string) in enumerate(s):
		if string == 'L':
			value.append(n - i - 1 - i)
			origional += i
		else:
			value.append(i - (n - i - 1))
			origional += n - i - 1
	value = sorted(value)[::-1]
	ans = []
	i = 0
	while i < n:
		if value[i] > 0:
			origional += value[i]
		ans.append(origional)
		i += 1
	return ' '.join([str(i) for i in ans])
t = int(input())
for T in range(t):
	n = int(input())
	s = input()
	print(solve(n, s))


N = int(input())
for k in range(N):
	len_s = int(input())
	s = input()
	res = []
	cur_res = 0
	list_analog = []
	for i in range(len_s):
		if s[i] == 'L':
			cur_res += i
			analog = len_s - 2 * i - 1
			if analog > 0:
				list_analog.append(analog)
		else:
			cur_res += len_s - i - 1
			analog = 2 * i - len_s + 1
			if analog > 0:
				list_analog.append(analog)
	list_analog.sort()
	res = []
	if len(list_analog) == 0:
		res.append(cur_res)
	for el in list_analog[::-1]:
		cur_res += el
		res.append(cur_res)
	while len(res) != len_s:
		res.append(res[-1])
	print(' '.join(map(str, res)))


def solve(num, line):
	count = []
	for i in range(num):
		if line[i] == 'L':
			count.append(i)
		else:
			count.append(num - i - 1)
	count.sort()
	current_sum = sum(count)
	sums = []
	for i in range(num):
		current_num = count[i]
		reversed_num = num - current_num - 1
		if reversed_num > current_num:
			current_sum = current_sum - current_num + reversed_num
		sums.append(str(current_sum))
	print(' '.join(sums))
t = int(input())
for i in range(t):
	n = int(input())
	dirs = input()
	solve(n, dirs)


import sys

def input(type=str):
	return type(sys.stdin.readline().strip())

def input_n(type=str):
	return list(map(type, input().split()))
t = input(int)
for _ in range(t):
	n = input(int)
	cmds = input()
	n = len(cmds)
	sum = 0
	for (i, cmd) in enumerate(cmds):
		if cmd == 'L':
			sum += i
		elif cmd == 'R':
			sum += n - 1 - i
	sums = []
	start = 0
	end = len(cmds) - 1
	while 0 <= start <= end < n:
		if cmds[start] == 'L':
			sum += -start + (n - 1 - start)
			sums.append(sum)
		start += 1
		if cmds[end] == 'R':
			sum += -(n - 1 - end) + end
			sums.append(sum)
		end -= 1
	if len(sums) == 0:
		sums.append(sum)
	while len(sums) < n:
		sums.append(sums[-1])
	print(' '.join(list(map(str, sums))))


for _ in range(int(input())):
	n = int(input())
	s = input()
	total = 0
	p = 0
	stack = []
	result = []
	for i in range(n):
		if i < n // 2:
			if s[i] == 'L':
				total += i
				stack.append(n - 1 - i * 2)
			else:
				total += n - 1 - i
		elif s[i] == 'R':
			total += n - 1 - i
			stack.append(i - (n - 1 - i))
		else:
			total += i
	stack.sort()
	while stack:
		total += stack.pop()
		result.append(total)
	m = len(result)
	if m < n:
		for i in range(n - m):
			result.append(total)
	print(' '.join(map(str, result)))


from sys import stdin
rd = stdin.readline
for _ in range(int(rd())):
	n = int(rd())
	s = rd().strip()
	res = []
	init = 0
	for i in range(n):
		if s[i] == 'R':
			init += n - i - 1
		else:
			init += i
	for i in range(n // 2):
		if s[i] == 'L':
			init += n - i - 1 - i
			res.append(str(init))
		if s[n - i - 1] == 'R':
			init += n - 1 - 2 * i
			res.append(str(init))
	while len(res) < n:
		res.append(str(init))
	print(' '.join(res))


import random

def sol(A):
	curr = 0
	for i in range(len(A)):
		if A[i] == 'L':
			curr += i
		else:
			curr += len(A) - i - 1
	i = 0
	j = len(A) - 1
	count = 0
	ans = []
	while i <= j and count < len(A):
		if i == len(A) - j - 1:
			if A[i] == 'L':
				curr += len(A) - i - 1 - i
				ans.append(curr)
				count += 1
			i += 1
		else:
			if A[j] == 'R':
				curr += j - (len(A) - j - 1)
				ans.append(curr)
				count += 1
			j -= 1
	ans = ans + [ans[-1]] * (len(A) - count) if count > 0 else [curr] * len(A)
	return ' '.join(map(str, ans))
x = int(input())
for _ in range(x):
	n = int(input())
	A = input()
	print(sol(A))


from operator import le

def solution(n, t):
	if n == 1:
		return 0
	person = []
	s = 1
	for i in t:
		if i == 'L':
			person.append(s - 1)
		else:
			person.append(n - s)
		s += 1
	total = sum(person)
	mid = n // 2
	left = [person[i] for i in range(n // 2) if t[i] == 'L']
	right = [person[i] for i in range(n // 2 + n % 2, n) if t[i] == 'R']
	left = left[::-1]
	res = []
	while len(right) + len(left):
		try:
			if left[-1] < right[-1]:
				total += n - 2 * left.pop() - 1
			else:
				total += n - 2 * right.pop() - 1
		except:
			if right:
				total += n - 2 * right.pop() - 1
			else:
				total += n - 2 * left.pop() - 1
		res.append(str(total))
	if len(res) == 0:
		return ' '.join([str(total)] * n)
	if len(res) != n:
		res = res + [res[-1]] * (n - len(res))
	return ' '.join(res)
N = int(input())
for _ in range(N):
	n = int(input())
	t = list(input())
	print(solution(n, t))


t = int(input())
for i in range(t):
	n = int(input())
	line = input()
	first_value = []
	m = n - 1
	for i in range(n):
		if line[i] == 'L':
			first_value.append(i)
		else:
			first_value.append(m - i)
	first_value.sort()
	k = sum(first_value)
	values = []
	for i in range(n):
		v1 = first_value[i]
		v2 = m - v1
		if v2 > v1:
			k -= v1
			k += v2
		values.append(str(k))
	print(' '.join(values))


from collections import defaultdict
t = int(input())

def solve():
	n = int(input())
	s = input()
	k = n // 2
	arr = []
	for i in range(n - 1, k - 1, -1):
		arr += [i]
	if n % 2 == 0:
		for i in range(k, n):
			arr += [i]
	else:
		for i in range(k + 1, n):
			arr += [i]
	brr = []
	for i in range(n):
		if s[i] == 'L':
			score = i
		else:
			score = n - 1 - i
		brr += [score]
	initial_score = sum(brr)
	crr = []
	for i in range(n):
		crr += [arr[i] - brr[i]]
	crr.sort(reverse=True)
	ans = []
	for i in range(n):
		ans += [crr[i] + initial_score]
		initial_score = ans[-1]
	print(' '.join((str(ele) for ele in ans)))
while t:
	solve()
	t -= 1


t = int(input())
result = []
for i in range(t):
	n = int(input())
	ch = input()
	test = []
	if n % 2 == 1:
		optimal = 'R' * (n // 2) + ch[n // 2] + 'L' * (n // 2)
	else:
		optimal = 'R' * (n // 2) + 'L' * (n // 2)
	sum = 0
	for j in range(len(ch)):
		if ch[j] == 'L':
			sum += j
		else:
			sum += n - 1 - j
	for j in range(len(ch) // 2):
		if ch[j] != optimal[j]:
			difference = n - 1 - 2 * j
			sum += difference
			test.append(str(sum))
		if ch[n - 1 - j] != optimal[n - 1 - j]:
			difference = n - 1 - j - j
			sum += difference
			test.append(str(sum))
	h = n - len(test)
	test = test + h * [str(sum)]
	result.append(' '.join(test))
for i in result:
	print(i)


for _ in range(int(input())):
	n = int(input())
	s = input()
	sum = 0
	a = []
	for i in range(n):
		if s[i] == 'L':
			cur = i
		else:
			cur = n - 1 - i
		sum += cur
		a.append(max(i, n - 1 - i) - cur)
	a.sort(reverse=True)
	ans = []
	for i in range(n):
		sum += a[i]
		ans.append(str(sum))
	print(' '.join(ans))


for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = []
	cur = 0
	for i in range(len(s)):
		if s[i] == 'L':
			arr.append(i)
		else:
			arr.append(len(s) - 1 - i)
		cur += arr[-1]
	arr.sort()
	res = []
	for i in range(len(arr)):
		new = len(s) - arr[i] - 1
		if new > arr[i]:
			cur += new - arr[i]
		res.append(str(cur))
	print(' '.join(res))


import sys

def helper(s, n):
	arr = []
	ssum = 0
	for i in range(n):
		if s[i] == 'L':
			arr.append(n - 1 - 2 * i)
			ssum += i
		else:
			ssum += n - 1 - i
			arr.append(2 * i + 1 - n)
	arr.sort(reverse=True)
	for i in range(1, n):
		arr[i] += arr[i - 1]
	ans = []
	for i in range(n):
		if i == 0:
			if arr[i] <= 0:
				ans.append(str(ssum))
			else:
				ans.append(str(ssum + arr[i]))
		elif arr[i] - arr[i - 1] <= 0:
			ans.append(str(ans[-1]))
		else:
			ans.append(str(ssum + arr[i]))
	return ans
input = sys.stdin.readline

def inp():
	print('Enter integer input here: ')
	return int(input())

def inlt():
	print('Enter list input here: ')
	return list(map(int, input().split()))

def insr():
	print('Enter string input here: ')
	return str(input())

def invr():
	print('Enter multiple integer input here: ')
	return map(int, input().split())
T = int(input())
for i in range(T):
	l = int(input())
	s = str(input())
	ans = helper(s, l)
	x = ' '.join(ans)
	print(x)


num_cases = int(input())
for i in range(num_cases):
	word_length = int(input())
	word = input()
	add_list = []
	score = 0
	for (j, dir) in enumerate(list(word)):
		to_left = j
		to_right = word_length - j - 1
		if dir == 'L':
			new = to_left
		if dir == 'R':
			new = to_right
		score += new
		add_list.append(max(to_left, to_right) - new)
	add_list.sort(reverse=True)
	out_list = []
	for j in add_list:
		score += j
		out_list.append(str(score))
	print(' '.join(out_list))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	_sum = 0
	deltas = []
	for i in range(n):
		if s[i] == 'L':
			_sum += i
			deltas.append(max(0, n - 1 - 2 * i))
		else:
			_sum += n - 1 - i
			deltas.append(max(0, 2 * i + 1 - n))
	deltas.sort(reverse=True)
	_ans = [_sum]
	for delta in deltas:
		_ans.append(_ans[-1] + delta)
	print(' '.join([str(i) for i in _ans[1:]]))


T = int(input())
for _ in range(T):
	l = int(input())
	a = input()
	current = 0
	for i in range(l):
		if a[i] == 'L':
			current += i
		else:
			current += l - i - 1
	if l % 2 == 1:
		i = l // 2
		j = 0
		arr = []
		while j < i:
			if a[j] == 'L':
				arr.append(j)
			if a[l - j - 1] == 'R':
				arr.append(l - j - 1)
			j += 1
	else:
		i = l // 2 - 1
		j = 0
		arr = []
		while j <= i:
			if a[j] == 'L':
				arr.append(j)
			if a[l - j - 1] == 'R':
				arr.append(l - j - 1)
			j += 1
	ans = []
	for i in arr:
		if i <= (l - 1) // 2:
			current += l - i - 1 - i
		else:
			current += i - l + i + 1
		ans.append(current)
	ans += [current] * (l - len(ans))
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	s = input()
	delta = []
	value = 0
	answer = []
	for (i, x) in enumerate(s):
		current = i if x == 'L' else n - 1 - i
		value += current
		best = max(i, n - 1 - i)
		delta.append(best - current)
	delta.sort(reverse=True)
	for k in range(n):
		value += delta[k]
		answer.append(value)
	print(' '.join([str(x) for x in answer]))


def f(n, s):
	numbers = []
	sum = 0
	for i in range(n):
		if s[i] == 'L':
			sum += i
		if s[i] == 'R':
			sum += n - 1 - i
	i = 0
	for k in range(1, n + 1):
		while i < n and s[i // 2 if i % 2 == 0 else n - 1 - i // 2] == ('R' if i % 2 == 0 else 'L'):
			i += 1
		if i == n:
			numbers.append(str(sum))
			continue
		if i % 2 == 0:
			sum += n - 1 - i // 2 - i // 2
		else:
			j = n - 1 - i // 2
			sum += j - (n - 1 - j)
		i += 1
		numbers.append(str(sum))
	return numbers
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	nums = f(n, s)
	print(' '.join(nums))


def cal(n, s):
	tot = 0
	p = []
	for i in range(n):
		if s[i] == 'L':
			tot += i
			p.append(n - i - 1 - i)
		else:
			tot += n - i - 1
			p.append(i - (n - i - 1))
	p.sort(reverse=True)
	ans = []
	for i in p:
		if i > 0:
			tot += i
			ans.append(tot)
		else:
			ans += [tot] * (n - len(ans))
			break
	return ans
for jj in range(int(input())):
	n = int(input())
	s = input()
	print(*cal(n, s))


for i in range(int(input())):
	n = int(input())
	s = input()
	cnt = 0
	res = []
	for i in range(n):
		if s[i] == 'L':
			cnt += i
		else:
			cnt += n - i - 1
	for i in range(n // 2):
		if s[i] == 'L':
			cnt = cnt + (n - i - 1 - i)
			res.append(cnt)
		if s[n - i - 1] == 'R':
			cnt = cnt + (n - i - 1 - i)
			res.append(cnt)
	if res:
		i = len(res)
		j = res[i - 1]
		while i < n:
			res.append(j)
			i += 1
	else:
		res = [cnt] * n
	print(*res)


def solve(s):

	def check_is_ideal(s):
		n = len(s)
		h = n // 2
		return s[:h] == 'R' * h and s[h + n % 2:] == 'L' * h

	def calc(s):
		ans = 0
		n = len(s)
		for i in range(len(s)):
			ans += i if s[i] == 'L' else n - i - 1
		return ans
	n = len(s)
	k = 0
	cur = calc(s)
	for i in range(n // 2):
		if s[i] == 'L':
			cur = cur - i + n - i - 1
			print(cur, end=' ')
			k += 1
		if s[n - i - 1] == 'R':
			cur = cur - i + n - i - 1
			print(cur, end=' ')
			k += 1
	print(((str(cur) + ' ') * (n - k))[:-1])
for _ in range(int(input())):
	input()
	solve(input())


for _ in range(int(input())):
	n = int(input())
	line = input()
	out_init = 0
	out = []
	for x in range(n):
		if line[x] == 'L':
			out_init += x
		if line[x] == 'R':
			out_init += n - x - 1
	for x in range(n):
		if line[x] == 'L':
			tmp1 = x
			tmp2 = n - x - 1
			if tmp2 > tmp1:
				out.append(tmp2 - tmp1)
		if line[x] == 'R':
			tmp2 = x
			tmp1 = n - x - 1
			if tmp2 > tmp1:
				out.append(tmp2 - tmp1)
	out = sorted(out, reverse=True)
	out2 = []
	for x in out:
		out2.append(out_init + x)
		out_init += x
	if not out:
		for x in range(n):
			out.append(out_init)
		print(' '.join([str(x) for x in out]))
		continue
	for x in range(n - len(out2)):
		out2.append(out2[-1])
	print(' '.join([str(x) for x in out2]))


__author__ = 'vipli'
t = int(input())
out = []
for i in range(t):
	n = int(input())
	line = str(input())
	this_count_sum = 0
	n_change_add = []
	for j in range(n):
		now_dir = line[j]
		now_count = j
		if now_dir == 'R':
			now_count = n - 1 - j
		this_count_sum += now_count
		now_max_c = max(j, n - 1 - j)
		n_change_add.append(now_max_c - now_count)
	n_change_add.sort(reverse=True)
	n_change_add[0] += this_count_sum
	for j in range(1, n):
		n_change_add[j] += n_change_add[j - 1]
	out.append(n_change_add)
for data in out:
	line = [str(v) for v in data]
	line = ' '.join(line)
	print(line)


import math

def inp():
	return int(input())

def inlt():
	return list(map(int, list(input().split(' '))))

def insr():
	s = input()
	return s
t = inp()
for _ in range(t):
	n = inp()
	people = insr()
	ans = []
	total = 0
	changes = []
	for i in range(n):
		direc = people[i]
		left = i
		right = n - i - 1
		if direc == 'L':
			total += left
			changes.append(right - left)
		else:
			total += right
			changes.append(left - right)
	changes.sort()
	ans = []
	prev = 0
	for i in range(1, n + 1):
		plus = max(0, changes[n - i])
		prev += plus
		ans.append(str(total + prev))
	print(' '.join(ans))


def val(a):
	ans = []
	for i in range(len(a)):
		if a[i] == 'L':
			ans.append(i)
		else:
			ans.append(len(a) - i - 1)
	return ans

def fun(a, k):
	an = []
	a = list(a)
	s = val(a)
	ln = len(a)
	sm = sum(s)
	i = 0
	j = len(a) - 1
	while i <= j:
		if a[i] == 'L':
			a[i] = 'r'
			sm += ln - i - 1
			sm -= s[i]
			an.append(sm)
		i += 1
		if a[j] == 'R':
			a[j] = 'l'
			sm += j
			sm -= s[j]
			an.append(sm)
		j -= 1
	if len(an) == 0:
		an = [sm]
	lna = len(an)
	for k in range(ln - lna):
		an.append(an[-1])
	return an
for _ in range(int(input())):
	l = int(input())
	n = input()
	print(*fun(n, l))


t = int(input())
for ncase in range(1, t + 1):
	n = int(input())
	s = input()
	diff = []
	score = []
	s0 = 0
	for i in range(n):
		if s[i] == 'L':
			diff.append(n - i - 1 - i)
			s0 += i
		else:
			diff.append(i - (n - i - 1))
			s0 += n - 1 - i
		if diff[i] < 0:
			diff[i] = 0
		else:
			diff[i] = diff[i]
	diff.sort(reverse=True)
	score.append(s0)
	for i in range(1, n + 1):
		score.append(score[i - 1] + diff[i - 1])
	print(' '.join((str(s) for s in score[1:])))


import heapq

def solve():
	x = int(input())
	for __ in range(x):
		n = int(input())
		st = list(str(input()))
		arr = [0] * len(st)
		hp = []
		s = 0
		for i in range(len(st)):
			if st[i] == 'L':
				arr[i] = i
				if i < n - i - 1:
					heapq.heappush(hp, -1 * (n - i - 1 - i))
			else:
				arr[i] = n - i - 1
				if n - i - 1 < i:
					heapq.heappush(hp, -1 * (i - (n - i - 1)))
			s += arr[i]
		count = 0
		res = []
		while hp and count < n:
			s -= heapq.heappop(hp)
			count += 1
			res.append(str(s))
		while count < n:
			count += 1
			res.append(str(s))
		print(' '.join(res))
solve()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	score = 0
	for (i, c) in enumerate(s):
		if c == 'L':
			score += i
		else:
			score += n - 1 - i
	scores = []
	(i, j) = (0, n - 1)
	for k in range(n):
		while s[i] == 'R' and i < n // 2:
			i += 1
		while s[j] == 'L' and j >= n // 2:
			j -= 1
		if i < n // 2 and i <= n - 1 - j:
			score += n - 2 * i - 1
			i += 1
		elif j >= n // 2 and i >= n - 1 - j:
			score += 2 * j - n + 1
			j -= 1
		scores.append(score)
	print(' '.join(map(str, scores)))


def count(peop):
	res = 0
	for p in range(len(peop)):
		if peop[p] == 'L':
			res += p
		else:
			res += len(peop) - p - 1
	return res
for _ in range(int(input())):
	length = int(input())
	people = input()
	results = []
	for i in range(length // 2):
		if people[i] == 'L':
			if results:
				results.append(results[-1] + length - 1 - i * 2)
			else:
				results.append(count(people) + length - 1 - i * 2)
		if people[(i + 1) * -1] == 'R':
			if results:
				results.append(results[-1] + length - 1 - i * 2)
			else:
				results.append(count(people) + length - 1 - i * 2)
	if len(results) == 0:
		results.append(count(people))
	while len(results) < len(people):
		results.append(results[-1])
	print(*results)


import heapq
output = []
t = int(input())
for i in range(t):
	cur = []
	(n, l) = (int(input()), input())
	count = 0
	h = []
	for j in range(n):
		if l[j] == 'L':
			count += j
			h.append(-(n - j - 1 - j))
		else:
			count += n - j - 1
			h.append(-(j - (n - j - 1)))
	heapq.heapify(h)
	while h:
		cv = -heapq.heappop(h)
		if cv > 0:
			count += cv
		cur.append(str(count))
	output.append('\t'.join(cur))
print('\n'.join(output))


def solve():
	n = int(input())
	s = input()
	l = []
	curSum = 0
	ret = []
	for i in range(0, n):
		if s[i] == 'L':
			curSum += i
			l.append(n - 1 - i - i)
		else:
			curSum += n - 1 - i
			l.append(i - (n - 1 - i))
	l.sort()
	for i in range(n - 1, -1, -1):
		if l[i] > 0:
			curSum += l[i]
		ret.append(curSum)
	print(*ret)
for _ in range(int(input())):
	solve()


T = int(input())

def solve():
	N = int(input())
	S = input()
	L = []
	for (i, s) in enumerate(S):
		if s == 'L':
			L.append(i)
		else:
			L.append(N - 1 - i)
	L.sort()
	cnt = sum(L)
	ret = []
	for i in range(N):
		cnt = max(cnt, cnt + N - 1 - L[i] - L[i])
		ret.append(cnt)
	print(*ret)
for _ in range(T):
	solve()


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	a = input().rstrip()
	if n % 2:
		value = n // 2
	else:
		value = 0
	deltas = []
	for idx in range(n // 2):
		if a[idx] == 'L':
			deltas.append(n - 1 - 2 * idx)
			value += idx
		else:
			value += n - 1 - idx
		if a[-(idx + 1)] == 'R':
			deltas.append(n - 1 - 2 * idx)
			value += idx
		else:
			value += n - 1 - idx
	if deltas:
		deltas.reverse()
	for k in range(n):
		if deltas:
			value += deltas.pop()
		print(value, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		if s[i] == 'L':
			ans += i
		else:
			ans += n - i - 1
	i = 0
	j = n - 1
	l = []
	k = 0
	while i < j:
		if s[i] == 'L':
			ans = ans - i + (n - i - 1)
			k += 1
			l.append(ans)
		if s[j] == 'R':
			ans = ans - (n - j - 1) + j
			k += 1
			l.append(ans)
		i += 1
		j -= 1
	ind = len(l) - 1
	for i in range(n - (ind + 1)):
		l.append(ans)
	print(*l)


for _ in range(int(input())):
	n = int(input())
	a = input()
	k = 0
	s = 0
	z = []
	for i in range(n):
		if a[i] == 'L':
			s += i
		else:
			s += n - i - 1
	for i in range(n // 2):
		if a[i] == 'L':
			s = s - i + (n - i - 1)
			z.append(s)
			k += 1
		if a[n - i - 1] == 'R':
			s = s - i + (n - i - 1)
			z.append(s)
			k += 1
	for i in range(k, n):
		z.append(s)
	print(*z)


def cnt_line(seq):
	cnt = 0
	for i in range(len(seq)):
		if seq[i] == 'R':
			cnt += len(seq) - i - 1
		else:
			cnt += i
	return cnt
n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	init_cnt = cnt_line(s)
	left = 0
	right = m - 1
	k = 0
	while left < right:
		if s[left] == 'R':
			left += 1
		else:
			init_cnt = init_cnt - left + (m - left - 1)
			print(init_cnt, end=' ')
			left += 1
			k += 1
		if left > right:
			break
		if s[right] == 'L':
			right -= 1
		else:
			init_cnt = init_cnt - (m - right - 1) + right
			print(init_cnt, end=' ')
			right -= 1
			k += 1
	while k < m:
		print(init_cnt, end=' ')
		k += 1
	print()


import math

def solve():
	n = int(input())
	lst = list(input())
	lst1 = []
	if n % 2:
		for i in reversed(range(n // 2 + 1, n)):
			lst1.append(i)
		lst1 = lst1 + [n // 2] + lst1[::-1]
	else:
		for i in reversed(range(n // 2, n)):
			lst1.append(i)
		lst1 = lst1 + lst1[::-1]
	lst2 = []
	for i in range(n):
		if lst[i] == 'R':
			lst2.append(n - i - 1)
		else:
			lst2.append(i)
	s1 = sum(lst1)
	s2 = sum(lst2)
	lst3 = []
	for i in range(n):
		lst3.append(lst1[i] - lst2[i])
	lst3.sort(reverse=True)
	for i in range(n):
		s2 += lst3[i]
		print(s2, end=' ')
	print()
t = int(input())
while t:
	t -= 1
	solve()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	line = input()
	score = 0
	possiblity = []
	for i in range(n // 2):
		if line[i] == 'L':
			score += i
			if i < n // 2:
				possiblity.append(n - 1 - 2 * i)
		else:
			score += n - 1 - i
	ind = n // 2
	if n % 2 == 1:
		ind += 1
		score += n // 2
	for i in range(ind, n):
		if line[i] == 'R':
			possiblity.append(2 * i + 1 - n)
			score += n - i - 1
		else:
			score += i
	possiblity.sort(reverse=True)
	diff = n - len(possiblity)
	for i in range(len(possiblity)):
		score += possiblity[i]
		print(score, end=' ')
	for i in range(diff):
		print(score, end=' ')
	print()


def main():
	for t in range(int(input())):
		n = int(input())
		s = input()
		a = []
		ans = 0
		for i in range(n):
			(x, y) = (0, 0)
			if s[i] == 'L':
				x = i
				y = n - 1 - i
			else:
				x = n - 1 - i
				y = i
			ans += x
			a.append(max(0, y - x))
		a.sort(reverse=True)
		for i in range(n):
			ans += a[i]
			print(ans, end=' ')
		print()
main()


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	temp = arr[0]
	for i in range(1, n):
		temp &= arr[i]
		arr[i] = temp
	for _ in range(q):
		arr1 = input().split()
		if len(arr1) == 1:
			continue
		(a, l, r, x) = map(int, arr1)
		ele = -1
		for i in range(l - 1, r):
			if arr[i] <= x:
				ele = max(ele, arr[i])
		print(ele)

def solve1():
	t = int(input())
	for _ in range(t):
		n = int(input())
		s = input()
		(l, r) = (0, n - 1)
		totalSum = 0
		arr = [0] * n
		for i in range(n):
			if s[i] == 'L':
				totalSum += l
				arr[i] = max(0, r - l)
			else:
				totalSum += r
				arr[i] = max(0, l - r)
			l += 1
			r -= 1
		arr.sort()
		re = [0] * n
		a = -1
		for i in range(n - 1, -1, -1):
			a += 1
			if arr[i] == 0:
				re[a] = totalSum
			else:
				totalSum += arr[i]
				re[a] = totalSum
		print(*re)

def main():
	t = int(input())
	for _ in range(t):
		solve()
solve1()


for i in range(int(input())):
	n = int(input())
	string = list(input())
	summ = 0
	for i in range(n):
		if string[i] == 'L':
			summ += i
		else:
			summ += n - i - 1
	count = 0
	for i in range(n // 2):
		if string[i] == 'L':
			summ = summ - i + n - i - 1
			print(summ, end=' ')
		else:
			count += 1
		if string[n - i - 1] == 'R':
			summ = summ - i + n - i - 1
			print(summ, end=' ')
		else:
			count += 1
	for i in range(count):
		print(summ, end=' ')
	if n % 2 != 0:
		print(summ, end=' ')
	print()


for _ in range(int(input())):
	lis = []
	leng = int(input())
	inp = list(input())
	lis2 = [0] * leng

	def L(y):
		return y

	def R(y):
		return leng - i - 1
	counter = 0
	for i in range(leng):
		x = inp[i]
		if x == 'L':
			counter += L(i)
			lis2[i] = L(i)
			lis.append(R(i) - lis2[i] if R(i) > lis2[i] else 0)
		elif x == 'R':
			counter += R(i)
			lis2[i] = R(i)
			lis.append(L(i) - lis2[i] if L(i) > lis2[i] else 0)
	lis3 = []
	for i in reversed(sorted(lis)):
		counter += i
		lis3.append(str(counter))
	print(' '.join(lis3))


for i in range(int(input())):
	n = int(input())
	stand = input()
	arr = []
	p1 = 0
	p2 = -1
	summ = 0
	for j in range(n // 2):
		if stand[p1] == 'R':
			summ += n - j - 1
		elif stand[p1] == 'L':
			summ += p1
			arr.append(n - 2 * j - 1)
		if stand[p2] == 'R':
			arr.append(n + p2 - (abs(p2) - 1))
			summ += -p2 - 1
		else:
			summ += n + p2
		p1 += 1
		p2 -= 1
	if n % 2 == 1:
		summ += n // 2
	arr.sort(reverse=True)
	arr2 = []
	for i in arr:
		summ += i
		arr2.append(summ)
	if len(arr2) == 0:
		arr2 = [summ] * n
	else:
		arr2 += (n - len(arr2)) * [arr2[-1]]
	print(*arr2)


t = int(input())
for i in range(t):
	n = int(input())
	L = input()
	mid = n // 2
	des = [0] * n
	curr = 0
	v_des = 0
	for i in range(n):
		if i < n // 2:
			des[i] = 'R'
			v_des += n - i - 1
		else:
			des[i] = 'L'
			v_des += i
	if n % 2 == 1:
		des[mid] = L[mid]
	change = []
	for i in range(n):
		if L[i] == 'L':
			curr += i
		if L[i] == 'L' and L[i] != des[i]:
			change.append(n - 1 - 2 * i)
		if L[i] == 'R':
			curr += n - i - 1
		if L[i] == 'R' and L[i] != des[i]:
			change.append(-n + 1 + 2 * i)
	change = sorted(change, reverse=True)
	ans = [v_des] * n
	for i in range(len(change) - 1):
		curr = curr + change[i]
		ans[i] = curr
	res = ' '.join([str(e) for e in ans])
	print(res)


t = int(input())
while t:
	n = int(input())
	s = input()
	insum = 0
	c = 0
	for i in range(0, n):
		if s[i] == 'L' and i > 0:
			insum = insum + i
		elif s[i] == 'R' and i != n - 1:
			insum = insum + (n - i - 1)
	for i in range(0, n // 2):
		if s[i] == 'L':
			insum = insum - i + (n - i - 1)
			print(insum, end=' ')
			c = c + 1
		if s[n - 1 - i] == 'R':
			insum = insum - i + (n - i - 1)
			print(insum, end=' ')
			c = c + 1
	if c != n:
		for i in range(0, n - c):
			print(insum, end=' ')
	print()
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	line = input()
	initial_score = 0
	scores = []
	for j in range(n):
		if line[j] == 'L':
			initial_score += j
			scores.append(n - 2 * j - 1)
		elif line[j] == 'R':
			initial_score += n - j - 1
			scores.append(2 * j - n + 1)
	scores.sort(reverse=True)
	val = prev_val = initial_score
	for score in scores:
		val += score
		if val > prev_val:
			prev_val = val
		else:
			val = prev_val
		print(val, end=' ')
	print('\r')


def solve():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(input())
		c = []
		tot = 0
		for i in range(1, n + 1):
			if a[i - 1] == 'R':
				tot += n - i
			else:
				tot += i - 1
		for i in range(1, n + 1):
			if a[i - 1] == 'L':
				c.append(n - i - (i - 1))
			else:
				c.append(i - 1 - (n - i))
		c.sort()
		c.reverse()
		for i in range(n):
			if c[i] > 0:
				tot += c[i]
			print(tot, end=' ')
		print()
solve()


for _ in range(int(input())):
	n = int(input())
	string = input()
	change = []
	sum = 0
	for i in range(n):
		if string[i] == 'L':
			change.append(n - 1 - i - i)
			sum += i
		else:
			change.append(i - (n - i - 1))
			sum += n - i - 1
	change.sort(reverse=True)
	for i in change:
		if i > 0:
			sum += i
		print(sum, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = []
	total = 0
	for i in range(n):
		if s[i] == 'L':
			res.append(n - 2 * i - 1)
			total += i
		else:
			res.append(2 * i - n + 1)
			total += n - i - 1
	res.sort(reverse=True)
	for v in res:
		if v > 0:
			total += v
		print(total, end=' ')
	print()


from heapq import *
t = int(input())
for _ in range(t):
	n = int(input())
	arrang = input()
	heap = []
	total = 0
	for (idx, a) in enumerate(arrang):
		(cur, poss) = (0, 0)
		if a == 'L':
			cur = idx
			poss = n - idx - 1
		else:
			cur = n - idx - 1
			poss = idx
		total += cur
		if poss > cur:
			heappush(heap, cur - poss)
	ans = []
	for change in range(1, n + 1):
		inc = 0
		if heap:
			inc += -heappop(heap)
			change -= 1
		total += inc
		ans.append(total)
	print(' '.join((str(val) for val in ans)))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	val = 0
	for i in range(n):
		if s[i] == 'L':
			val += i
		else:
			val += n - i - 1
	k = n
	(l, r) = (0, len(s) - 1)
	while k >= 0 and l <= r:
		if s[l] == 'L':
			k -= 1
			val += n - l - 1 - l
			print(val, end=' ')
		l += 1
		if s[r] == 'R':
			k -= 1
			val += r - (n - r - 1)
			print(val, end=' ')
		r -= 1
	for i in range(k):
		print(val, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(input())
	cur_val = 0
	for i in range(n // 2):
		if arr[i] == 'L':
			cur_val += i
		elif arr[i] == 'R':
			cur_val += n - i - 1
		if arr[-i - 1] == 'R':
			cur_val += i
		elif arr[-i - 1] == 'L':
			cur_val += n - i - 1
	if n % 2:
		cur_val += n // 2
	mis_vals = []
	for i in range(n // 2):
		if arr[i] == 'L':
			mis_vals.append(n - i - 1 - i)
		if arr[-i - 1] == 'R':
			mis_vals.append(n - i - 1 - i)
	rem = n - len(mis_vals)
	mis_vals.sort(reverse=True)
	res = []
	for x in mis_vals:
		cur_val += x
		res.append(cur_val)
	if res:
		res.extend(rem * [res[-1]])
	else:
		res.extend(rem * [cur_val])
	print(*res)


def summ(s, n):
	total = 0
	for i in range(n):
		if s[i] == 'L':
			total += i
		else:
			total += n - 1 - i
	return total
t = int(input())
while t != 0:
	n = int(input())
	s = input()
	total = summ(s, n)
	k = n
	ans = []
	for i in range(int(n / 2)):
		if s[i] != 'R' and k != 0:
			total -= i
			total += n - 1 - i
			ans.append(total)
			k -= 1
		if s[n - 1 - i] != 'L' and k != 0:
			total -= i
			total += n - 1 - i
			ans.append(total)
			k -= 1
	while k != 0:
		ans.append(total)
		k -= 1
	print(*ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	su = 0
	b = []
	a = []
	for i in range(n):
		if s[i] == 'L':
			su += i
			a.append(n - i - 1 - i)
		else:
			su = su + (n - i - 1)
			a.append(i - (n - 1 - i))
	a.sort(reverse=True)
	for i in range(n):
		if a[i] > 0:
			su = su + a[i]
			b.append(su)
		else:
			b.append(su)
	print(*b)


test = int(input())
for t in range(test):
	n = int(input())
	s = input()
	s = [*s]
	score = 0
	score_list = list()
	for i in range(n):
		if s[i] == 'R':
			score += n - (1 + i)
			score_list.append(n - (1 + i))
		else:
			score += i
			score_list.append(i)
	ind = 1
	score_p = list()
	for i in range(1, n + 1):
		while ind <= n // 2:
			if s[ind - 1] == 'L':
				s[ind - 1] = 'R'
				score += n - (ind + score_list[ind - 1])
				score_list[ind - 1] = n - ind
				break
			elif s[-ind] == 'R':
				s[-ind] = 'L'
				score += n - (ind + score_list[-ind])
				score_list[-ind] = n - ind
				break
			ind += 1
		score_p.append(str(score))
	to_p = ' '.join(score_p)
	print(to_p)


def solve():
	n = int(input())
	str = input()
	count = []
	count1 = []
	sum = 0
	for i in range(n):
		if str[i] == 'R':
			sum += n - i - 1
		else:
			sum += i
		if i < n - i - 1 and str[i] == 'L':
			count.append(n - 1 - i - i)
		elif i > n - i - 1 and str[i] == 'R':
			count.append(i + i + 1 - n)
	count = sorted(count)[::-1]
	sm = 0
	for i in range(len(count)):
		sm += count[i]
		count1.append(sm + sum)
	for i in range(len(count), n):
		count1.append(sm + sum)
	for i in range(len(count1)):
		print(count1[i], end=' ')
	print()
t = int(input())
for i in range(t):
	solve()


for i in range(int(input())):
	n = int(input())
	row = input()
	dif = []
	mid = n / 2 - 1 + 0.1
	s = 0
	for j in range(n):
		if j < mid:
			if row[j] == 'R':
				s += n - 1 - j
				dif.append(0)
			else:
				s += j
				dif.append(n - 1 - j - j)
		elif row[j] == 'R':
			s += n - 1 - j
			dif.append(j - (n - 1 - j))
		else:
			s += j
			dif.append(0)
	dif = sorted(dif, reverse=True)
	for i in dif:
		s += i
		print(s, end=' ')
	print('\n')


class Line:

	def solve(self, N, arrangement):
		value = 0
		updates = []
		for i in range(N):
			if arrangement[i] == 'L':
				if N - i - 1 > i:
					updates.append(N - 2 * i - 1)
				value += i
			else:
				if i > N - i - 1:
					updates.append(2 * i - N + 1)
				value += N - i - 1
		updates.sort()
		for i in range(1, N + 1):
			if len(updates) > 0:
				value += updates.pop()
			print(value, end=' ')
		print()
		return
T = int(input())
while T:
	T -= 1
	N = int(input())
	arrangement = list(input())
	Line().solve(N, arrangement)


t = int(input())
for t in range(t):
	(n, s) = (int(input()), input())
	(tot, opt) = (0, [])
	for i in range(n):
		r = n - i - 1
		if s[i] == 'R':
			tot += r
			opt.append(i - r if r < i else 0)
		else:
			tot += i
			opt.append(r - i if i < r else 0)
	sums = []
	i = 0
	opt.sort()
	while i < n:
		o = opt.pop()
		tot += o
		sums.append(tot)
		i += 1
	print(*sums)


t = int(input())
for _ in range(t):
	(n, s) = (int(input()), input())
	(tot, opt) = (0, [])
	for i in range(n):
		r = n - i - 1
		if s[i] == 'R':
			tot += r
			opt.append(i - r if r < i else 0)
		else:
			tot += i
			opt.append(r - i if i < r else 0)
	sums = []
	opt.sort()
	for i in range(n - 1, -1, -1):
		tot += opt[i]
		sums.append(tot)
	print(*sums)


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	new_arr = []
	ans = 0
	for i in range(n):
		if s[i] == 'L':
			new_arr.append(n - 1 - i - i)
			ans += i
		else:
			new_arr.append(i - (n - 1 - i))
			ans += n - 1 - i
	new_arr.sort()
	for i in new_arr[::-1]:
		if i >= 0:
			ans += i
			print(ans, end=' ')
		else:
			print(ans, end=' ')
	print()


from collections import Counter

def main():
	for _ in range(int(input())):
		n = int(input())
		string = input()
		half = n // 2
		arr = []
		for i in range(n):
			if string[i] == 'L':
				arr.append(i)
			else:
				arr.append(n - i - 1)
		arr.sort()
		sm = sum(arr)
		ans = []
		for i in range(n):
			if arr[i] < half:
				sm -= arr[i]
				sm += n - arr[i] - 1
				ans.append(sm)
			else:
				ans.append(sm)
		for i in ans:
			print(i, end=' ')
		print()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = 0
	r = n - 1
	cur = 0
	for i in range(n):
		if s[i] == 'L':
			cur += i
		else:
			cur += n - i - 1
	result = [0 for i in range(n + 1)]
	result[0] = cur
	k = 1
	for i in range(n // 2):
		if s[i] == 'L' or s[n - i - 1] == 'R':
			if s[i] == 'L':
				result[k] = result[k - 1] - i + n - i - 1
				k += 1
			if s[n - i - 1] == 'R':
				result[k] = result[k - 1] - i + n - i - 1
				k += 1
	while k <= n:
		result[k] = result[k - 1]
		k += 1
	print(*result[1:])


for caseno in range(int(input())):
	n = int(input())
	s = input()
	values = []
	for i in range(n):
		if s[i] == 'L':
			values += [i]
		else:
			values += [n - 1 - i]
	values = sorted(values)
	total = sum(values)
	answers = []
	curr_answer = total
	for i in range(n):
		curr = values[i]
		mod_curr = n - 1 - curr
		if mod_curr > curr:
			curr_answer = curr_answer - curr + mod_curr
		answers += [curr_answer]
	print(*answers)


for x in range(int(input())):
	n = int(input())
	s = input()
	sm = 0
	for x in range(len(s)):
		if s[x] == 'R':
			sm += n - (x + 1)
		else:
			sm += x
	l = 0
	r = n - 1
	arr = []
	k = n
	while l <= r and k > 0:
		c = 1
		if s[l] == 'L' and k > 0:
			k -= 1
			sm += n - 2 * l - 1
			arr.append(sm)
		if s[r] == 'R' and k > 0:
			k -= 1
			sm += r - (n - (r + 1))
			arr.append(sm)
		l += 1
		r -= 1
	if len(arr) == 0:
		arr = [sm] * n
	else:
		a = [arr[-1]] * (n - len(arr))
		arr += a
	print(*arr)


def find_best_dir(s1, n):
	ans = []
	for i in range(n // 2):
		if s1[i] == 'L':
			ans.append(n - i - 1 - i)
		if s1[-i - 1] == 'R':
			j = n - i - 1
			ans.append(j - (n - j - 1))
	return ans

def res(s1, n):
	ans = []
	cur_sum = 0
	for i in range(n):
		if s1[i] == 'R':
			cur_sum += n - i - 1
		else:
			cur_sum += i
	best_extr_s = find_best_dir(s1, n)
	for j in range(n):
		if j < len(best_extr_s):
			extra_sum = best_extr_s[j]
		else:
			extra_sum = 0
		ans.append(cur_sum + extra_sum)
		cur_sum = cur_sum + extra_sum
	return ans
n = int(input())
for _ in range(n):
	n1 = int(input())
	s1 = input()
	print(*res(s1, n1))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	sum = 0
	cng = []
	for i in range(n):
		if s[i] == 'L':
			sum += i
			cng.append(n - i - 1 - i)
		else:
			sum += n - i - 1
			cng.append(i - (n - i - 1))
	cng.sort(reverse=True)
	impr = []
	for k in range(n):
		if cng[k] > 0:
			sum += cng[k]
		impr.append(sum)
	print(*impr)


for _ in range(int(input())):
	n = int(input())
	s = input()
	id = 'R' * (n // 2)
	if n & 1:
		id += 'R'
	id += 'L' * (n // 2)
	intial = 0
	for i in range(n):
		if s[i] == 'R':
			intial += n - i - 1
		else:
			intial += i
	(i, j) = (0, n - 1)
	ans = []
	for k in range(n):
		if k % 2 == 0:
			if s[i] == 'L':
				intial = intial - i + n - i - 1
				ans.append(intial)
			i += 1
		else:
			if s[j] == 'R':
				intial = intial - (n - j - 1) + j
				ans.append(intial)
			j -= 1
	x = intial
	for i in range(len(ans), n):
		ans.append(x)
	print(*ans)


t = int(input())
for i in range(t):
	n = int(input())
	q = input()
	l = len(q)
	m = l // 2
	it = 0
	for k in range(l):
		if q[k] == 'L':
			it += k
		else:
			it += l - k - 1
	c = 0
	for k in range(m):
		if q[k] == 'L':
			it += l - k - 1 - k
			print(it, end=' ')
			c += 1
		if q[l - k - 1] == 'R':
			it += l - k - 1 - (l - (l - k - 1) - 1)
			print(it, end=' ')
			c += 1
	for ee in range(l - c):
		print(it, end=' ')
	print()


t = int(input())
while t > 0:
	n = int(input())
	line = input()
	ans = 0
	change = [0] * n
	for i in range(n):
		if line[i] == 'L':
			ans += i
			change[i] = n - i - 1 - i
		else:
			ans += n - i - 1
			change[i] = i - (n - i - 1)
	change.sort()
	for i in range(n - 1, -1, -1):
		if change[i] > 0:
			ans += change[i]
		print(ans, end=' ')
	print()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		if s[i] == 'L':
			ans += i
		else:
			ans += n - i - 1
	a = []
	for i in range(n // 2):
		if s[i] == 'L':
			a.append(n - i - i - 1)
		else:
			a.append(0)
	if n % 2 != 0:
		a.append(0)
	for i in range((n + 1) // 2, n):
		if s[i] == 'R':
			a.append(i - n + i + 1)
		else:
			a.append(0)
	a.sort(reverse=True)
	for x in a:
		ans += x
		print(ans, end=' ')
	print('')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	arr = []
	sum = 0
	for j in range(n):
		if s[j] == 'L':
			c = n - 2 * j - 1
			sum += j
		else:
			c = 2 * j + 1 - n
			sum += n - 1 - j
		arr.append(c)
	arr.sort(reverse=True)
	res = []
	k = sum
	for j in range(n):
		if arr[j] > 0:
			k += arr[j]
		res.append(k)
	print(*res)


for Pythonic__Python in range(int(input())):
	n = int(input())
	d = input()
	l = []
	ans = 0
	for i in range(n):
		if d[i] == 'L':
			l.append(n - 1 - i - i)
			ans += i
		else:
			l.append(i - (n - 1 - i))
			ans += n - 1 - i
	l.sort()
	for i in l[::-1]:
		if i >= 0:
			ans += i
			print(ans, end=' ')
		else:
			print(ans, end=' ')
	print()


testcase = int(input())
for _ in range(testcase):
	n = int(input())
	line = input()
	turnaround = list()
	originalsum = 0
	for i in range(n):
		if line[i] == 'L':
			turnaround.append(n - 1 - i - i)
			originalsum += i
		else:
			turnaround.append(i - (n - 1 - i))
			originalsum += n - 1 - i
	turnaround.sort(reverse=True)
	for i in range(n):
		if turnaround[i] > 0:
			originalsum += turnaround[i]
		print(originalsum, end=' ')
	print()


t = int(input())
for o in range(t):
	n = int(input())
	a = [0 for i in range(n)]
	s = input()
	(num, idx, ans) = (0, -1, 0)
	for j in range(n):
		if s[j] == 'L':
			num += j
			a[j] = n - j * 2 - 1
		else:
			num += n - j - 1
			a[j] = j * 2 + 1 - n
	a.sort()
	for i in range(n - 1, -1, -1):
		if a[i] > 0:
			num += a[i]
		print(num, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	line = 'R' * (n // 2) + ('R' if n % 2 == 1 else '') + 'L' * (n // 2)
	(b, e) = (0, len(s) - 1)
	k = 1
	res = sum([i if c == 'L' else n - i - 1 for (i, c) in enumerate(s)])
	while b < e:
		if (s[b], s[e]) == ('L', 'R'):
			res += n - 2 * b - 1
			b += 1
			print(res, end=' ')
			k += 1
			res += 2 * e - n + 1
			e -= 1
			print(res, end=' ')
			k += 1
		elif (s[b], s[e]) == ('R', 'R'):
			res += 2 * e - n + 1
			print(res, end=' ')
			b += 1
			e -= 1
			k += 1
		elif (s[b], s[e]) == ('L', 'L'):
			res += n - 2 * b - 1
			print(res, end=' ')
			b += 1
			e -= 1
			k += 1
		else:
			b += 1
			e -= 1
	for _ in range(n - k + 1):
		print(res, end=' ')
	print()


t = int(input())
l = []
s = []
for i in range(t):
	l.append(int(input()))
	s.append(input())
for i in range(t):
	if l[i] % 2 == 0:
		k = 0
		sum = 0
		mas = []
		for j in range(l[i]):
			if s[i][j] == 'R':
				sum += l[i] - (j + 1)
			else:
				sum += j
		for j in range(l[i] // 2):
			if s[i][j] == 'L':
				k += 1
				sum += -2 * j - 1 + l[i]
				mas.append(sum)
			j1 = l[i] - 1 - j
			if s[i][j1] == 'R':
				k += 1
				sum += 2 * j1 + 1 - l[i]
				mas.append(sum)
		while k < l[i]:
			k += 1
			mas.append(sum)
		print(*mas)
	else:
		k = 0
		sum = 0
		mas = []
		for j in range(l[i]):
			if s[i][j] == 'R':
				sum += l[i] - (j + 1)
			else:
				sum += j
		for j in range(l[i] // 2):
			if s[i][j] == 'L':
				k += 1
				sum += -2 * j - 1 + l[i]
				mas.append(sum)
			j1 = l[i] - 1 - j
			if s[i][j1] == 'R':
				k += 1
				sum += 2 * j1 + 1 - l[i]
				mas.append(sum)
		while k < l[i]:
			k += 1
			mas.append(sum)
		print(*mas)


def getDifference(people):
	n = len(people)
	result = []
	for (index, person) in enumerate(people):
		if person == 'L':
			result.append(n - index - 1 - index)
		else:
			result.append(index - (n - index - 1))
	result.sort(reverse=True)
	return result

def getCurrentSum(people):
	n = len(people)
	totalSum = 0
	for (index, person) in enumerate(people):
		if person == 'L':
			totalSum += index
		else:
			totalSum += n - index - 1
	return totalSum
t = int(input())
for _ in range(t):
	n = int(input())
	people = list(input())
	oldSum = getCurrentSum(people=people)
	diffList = getDifference(people=people)
	for k in range(n):
		if diffList[k] > 0:
			currSum = oldSum + diffList[k]
		else:
			currSum = oldSum
		print(currSum, end=' ')
		oldSum = currSum
	print('')


def implementation(length, data):
	if length == 1:
		print(0)
		return
	line = []
	for i in range(length):
		if data[i] == 'L':
			line.append(i)
		else:
			line.append(length - i - 1)
	line.sort()
	final = sum(line)
	for i in range(0, length):
		if length - 1 - line[i] >= line[i]:
			final -= line[i]
			final += length - 1 - line[i]
		print(final, end=' ')
	print()
t = int(input())
for i in range(t):
	length = int(input())
	data = input()
	implementation(length, data)


for t in range(int(input())):
	n = int(input())
	s = list(input())
	i = 0
	j = n - 1
	summ = 0
	for i in range(n):
		if s[i] == 'L':
			summ += i
		else:
			summ += n - i - 1
	ans = []
	i = 0
	j = n - 1
	while i < j:
		if i < n // 2:
			if s[i] == 'L':
				prev_value = i
				next_value = n - i - 1
				summ = summ - prev_value + next_value
				ans.append(summ)
			i += 1
		if j >= n // 2:
			if s[j] == 'R':
				prev_value = n - j - 1
				next_value = j
				summ = summ - prev_value + next_value
				ans.append(summ)
			j -= 1
	rem = [summ] * (n - len(ans))
	ans += rem
	print(*ans)


for t in range(int(input())):
	n = int(input())
	s = input()
	a = []
	count = 0
	for i in range(n):
		l = i
		r = n - i - 1
		if s[i] == 'L':
			a.append(r - l)
			count += l
		else:
			a.append(l - r)
			count += r
	a = sorted(a, reverse=True)
	for i in range(n):
		if a[i] > 0:
			count += a[i]
		print(count, end=' ')
	print()


t = int(input())
for i in range(0, t):
	n = int(input())
	s = list(input())
	a = 0
	b = 0
	for j in range(0, n):
		if s[j] == 'L':
			a += j
		else:
			a += n - 1 - j
	if n % 2 != 0:
		for j in range(0, n // 2):
			if s[j] == 'L':
				s[j] = 'R'
				a = a + n - 1 - 2 * j
				print(a, end=' ')
				b += 1
			if s[n - 1 - j] == 'R':
				s[j] = 'L'
				a = a + n - 1 - 2 * j
				print(a, end=' ')
				b += 1
		while b < n:
			print(a, end=' ')
			b += 1
	else:
		for j in range(0, n // 2):
			if s[j] == 'L':
				s[j] = 'R'
				a = a + n - 1 - 2 * j
				b += 1
				print(a, end=' ')
			if s[n - j - 1] == 'R':
				s[j] = 'L'
				a = a + n - 1 - 2 * j
				print(a, end=' ')
				b += 1
		while b < n:
			print(a, end=' ')
			b += 1
	print(' ')


from math import floor, ceil
num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()

def change(n, i):
	return abs(n - 2 * i - 1)
t = num_inp()
for _ in range(t):
	n = num_inp()
	s = str_inp()
	ind = []
	val = floor(n / 2)
	req = ['R' for _ in range(val)]
	req += ['L' for _ in range(n - val)]
	if n % 2 == 1:
		req[val] = s[val]
	initial = 0
	for i in range(n):
		if s[i] == 'R':
			initial += n - i - 1
		else:
			initial += i
	count = 0
	ind = []
	for i in range(n):
		if s[i] != req[i]:
			ind.append(i)
	p1 = 0
	p2 = len(ind) - 1
	l = []
	while p1 <= p2:
		v1 = change(n, ind[p1])
		v2 = change(n, ind[p2])
		if v1 > v2:
			initial += v1
			l.append(initial)
			p1 += 1
		else:
			initial += v2
			l.append(initial)
			p2 -= 1
	print(' '.join(map(str, l)), end=' ')
	for i in range(n - len(l)):
		print(initial, end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = input()
	c = 0
	x = []
	for i in range(n):
		if a[i] == 'L':
			c += i
			if n - i - 1 > i:
				x.append(n - 2 * i - 1)
		else:
			c += n - i - 1
			if i > n - i - 1:
				x.append(2 * i - n + 1)
	x.sort(reverse=True)
	k = len(x)
	y = []
	for i in range(n):
		if i < k:
			c += x[i]
		y.append(c)
	print(*y)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	string = str(input())
	lst = []
	curr_score = 0
	for i in range(len(string)):
		if string[i] == 'L':
			curr_score += i
			itm = n - i - 1 - i
		else:
			curr_score += n - i - 1
			itm = i - n + i + 1
		if n % 2 != 0 and i == int(n / 2):
			lst.append(0)
		else:
			lst.append(itm)
	lst.sort(reverse=True)
	for i in range(n):
		if lst[i] > 0:
			curr_score += lst[i]
		print(curr_score, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = []
	y = 0
	for i in range(n):
		if s[i] == 'L':
			y += i
			a.append(n - i - 1 - i)
		else:
			y += n - i - 1
			a.append(i - (n - i - 1))
	a.sort(reverse=True)
	b = []
	for i in range(n):
		y += max(a[i], 0)
		b.append(y)
	print(*b)


for _ in range(int(input())):
	l = int(input())
	st = input()
	sch = 0
	izm = []
	for i in range(l):
		if st[i] == 'L':
			sch += i
			izm.append(l - i - 1 - i)
		else:
			sch += l - i - 1
			izm.append(i - (l - i - 1))
	izm.sort(reverse=True)
	otv = [0] * l
	otv[0] = max(sch, sch + izm[0])
	for i in range(1, l):
		if izm[i] > 0:
			otv[i] = otv[i - 1] + izm[i]
		else:
			otv[i] = otv[i - 1]
	print(*otv)