← 返回题目列表

Codeforces · 2048/I1

I1. 凯文和谜题(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,您需要找到任何一个好的数组。只有解决了该问题的所有版本,您才能破解。

凯文正在参观红教堂,他在墙上发现了一个谜题。

对于数组 $$$ a $$$,令 $$$ c(l,r) $$$ 表示 $$$ a_l, a_{l+1}, \ldots, a_r $$$ 中有多少个不同的数字。特别是,如果 $$$ l > r $$$,则定义 $$$ c(l,r) = 0 $$$。

给定一个字符串 $$$ s $$$,长度为 $$$ n $$$,仅由字母 $$$ \texttt{L} $$$ 和 $$$ \texttt{R} $$$ 组成。如果 $$$ 1 \leq i \leq n $$$ 满足以下条件,则称非负数组 $$$ a $$$ 为好数组:

- 如果 $$$s_i=\verb!L!$$$,则 $$$c(1,i-1)=a_i$$$;
- 如果 $$$s_i=\verb!R!$$$,则 $$$c(i+1,n)=a_i$$$。

如果有一个好的数组 $$$a$$$,则打印任何一个好的数组。否则,报告不存在这样的数组。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个字符串$$$s$$$,长度为$$$n$$$,仅包含英文大写字母$$$\verb!L!$$$和$$$\verb!R!$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果存在一个好的数组,则打印 $$$n$$$ 非负整数:一个好的数组 $$$a$$$。否则,打印单个整数 $$$-1$$$。

如果有多个数组$$$a$$$满足条件,则可以输出任意一个。

示例

输入 #1

4
3
LLR
3
RRL
4
RRLR
5
LLRLR

输出 #1

0 1 0
2 1 2
-1
0 1 2 3 0

注意

在第一个测试用例中,数组 $$$[0,1,0]$$$ 满足条件,因为:

- 当 $$$i=1$$$、$$$s_i=\verb!L!$$$ 且 $$$c(1,0)=0$$$ 时;
- 当 $$$i=2$$$、$$$s_i=\verb!L!$$$ 和 $$$c(1,1)=1$$$ 时,因为 $$$a_1$$$ 中只有一个不同的数字;
- 当 $$$i=3$$$、$$$s_i=\verb!R!$$$ 且 $$$c(4,3)=0$$$ 时。

在第二个测试用例中,另一个合适的答案是$$$[1,1,1]$$$。

在第三个测试用例中,可以证明不存在满足条件的数组。