I1. Kevin and Puzzle (Easy Version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

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

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.

Example
Input
4
3
LLR
3
RRL
4
RRLR
5
LLRLR
Output
0 1 0
2 1 2
-1
0 1 2 3 0
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.