Kevin and Puzzle (Easy Version)
Contest: Codeforces Global Round 28
Difficulty rating: 3500
Tags: constructive algorithms

This is the easy version of the problem. The difference between the versions is that in this version, you need to find any one good array. You can hack only if you solved all versions of this problem.

Kevin is visiting the Red Church, and he found a puzzle on the wall.

For an array $$$ a $$$, let $$$ c(l,r) $$$ indicate how many distinct numbers are among $$$ a_l, a_{l+1}, \ldots, a_r $$$. In particular, if $$$ l > r $$$, define $$$ c(l,r) = 0 $$$.

You are given a string $$$ s $$$ of length $$$ n $$$ consisting of letters $$$ \texttt{L} $$$ and $$$ \texttt{R} $$$ only. Let a non-negative array $$$ a $$$ be called good, if the following conditions hold for $$$ 1 \leq i \leq n $$$:

- if $$$s_i=\verb!L!$$$, then $$$c(1,i-1)=a_i$$$;
- if $$$s_i=\verb!R!$$$, then $$$c(i+1,n)=a_i$$$.

If there is a good array $$$a$$$, print any of the good arrays. Otherwise, report that no such arrays exists.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of string $$$s$$$.

The second line of each test case contains a string $$$s$$$ with a length $$$n$$$, containing only English uppercase letters $$$\verb!L!$$$ and $$$\verb!R!$$$.

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

Output format:
For each test case, if a good array exists, print $$$n$$$ non-negative integers: a good array $$$a$$$. Otherwise, print a single integer $$$-1$$$.

If there are multiple arrays $$$a$$$ satisfying the conditions, you can output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the array $$$[0,1,0]$$$ satisfies the conditions because:

- When $$$i=1$$$, $$$s_i=\verb!L!$$$, and $$$c(1,0)=0$$$;
- When $$$i=2$$$, $$$s_i=\verb!L!$$$, and $$$c(1,1)=1$$$, since there is only one distinct number in $$$a_1$$$;
- When $$$i=3$$$, $$$s_i=\verb!R!$$$, and $$$c(4,3)=0$$$.

In the second test case, another suitable answer is $$$[1,1,1]$$$.

In the third test case, it can be proven that there's no array satisfying the conditions.

Example input:
4
3
LLR
3
RRL
4
RRLR
5
LLRLR

Example output:
0 1 0
2 1 2
-1
0 1 2 3 0

Editorial:
Hint #1: Consider the leftmost and rightmost characters, and recursively construct the sequence.
Lemma: Suppose the largest value filled is $$$mx$$$, and the number of distinct values is $$$c$$$. Let $$$d = c - mx$$$. Then, $$$d = 0$$$ or $$$d = 1$$$.
Proof: Clearly, $$$c \le mx + 1$$$. If $$$c < mx$$$, observe where $$$mx$$$ is placed, and a contradiction arises.
Now, consider the leftmost and rightmost characters in sequence $$$s$$$:
• If they are $$$L$$$ and $$$R$$$, we can see that both positions must be filled with $$$0$$$, and no other position can be filled with $$$0$$$. For internal positions, whether $$$L$$$ or $$$R$$$, $$$0$$$ counts as a distinct number. Therefore, we can remove these two positions, recursively solve for the remaining part, add $$$1$$$ to all numbers, and then place a $$$0$$$ at both ends.
• If both are $$$L$$$, the leftmost $$$L$$$ must be $$$0$$$. Suppose the rightmost $$$L$$$ is filled with $$$x$$$. It is easy to prove that $$$x$$$ cannot be placed in internal positions. For internal positions, whether $$$L$$$ or $$$R$$$, either $$$0$$$ or $$$x$$$ is counted as a distinct number. So, as in the previous case, we remove the two positions, recursively solve for the remaining part, add $$$1$$$ to all numbers, and then add $$$0$$$ and $$$x$$$ at both ends. The value of $$$x$$$ must be the number of distinct values inside plus 1. This condition is equivalent to the internal region satisfying $$$d = 1$$$.
• If both are $$$R$$$, the analysis is the same as for the $$$L$$$ and $$$L$$$ case.
• If the leftmost character is $$$R$$$ and the rightmost character is $$$L$$$, a simple construction is to fill everything with $$$1$$$. In this case, no $$$0$$$ will appear, so this case can only correspond to $$$d = 0$$$.
We recursively remove the leftmost and rightmost characters, solve for the inner region, add $$$1$$$ to all of them, and place $$$0$$$ and $$$x$$$ at both ends.
Now, consider how $$$d$$$ changes:
• For the $$$LR$$$ case, $$$d$$$ remains unchanged.
• For $$$LL$$$ or $$$RR$$$, the internal region must satisfy $$$d = 1$$$.
• For $$$RL$$$, the entire region results in $$$d = 0$$$.
Therefore, consider the outermost $$$RL$$$. If it contains $$$LL$$$ or $$$RR$$$ inside, there is no solution.
Otherwise, a solution always exists, and it can be easily constructed based on the above process, the time complexity is $$$O(n)$$$.