塔利亚是一位传奇的国际象棋大师。她有 $$$n$$$ 奖杯,排成一排,编号从 $$$1$$$ 到 $$$n$$$(从左到右),每个奖杯旁边立着一盏灯(灯被编号为奖杯)。
一盏灯可以指向左侧或右侧,它会照亮该方向上的所有奖杯(但不会照亮旁边的奖杯)。更正式地说,Thalia 有一个字符串 $$$s$$$ 仅由字符“L”和“R”组成,表示灯的当前方向。灯 $$$i$$$ 亮起:
- 奖杯 $$$1,2,\ldots, i-1$$$ 如果 $$$s_i$$$ 为“L”;
- 奖杯$$$i+1,i+2,\ldots, n$$$(如果$$$s_i$$$ 为“R”)。
她最多可以执行一次以下操作:
- 选择一个索引 $$$i$$$ ($$$1 \leq i < n$$$);
- 交换灯 $$$i$$$ 和 $$$i+1$$$ (不改变它们的方向)。也就是说,将 $$$s_i$$$ 与 $$$s_{i+1}$$$ 交换。
塔莉亚要求你照亮她所有的奖杯(让每个奖杯至少被一盏灯照亮),或者告诉她这是不可能的。如果可能,您可以选择执行操作或不执行任何操作。请注意,灯不能改变方向,只能交换相邻的灯。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — 奖杯数量。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符“L”和“R”——第 $$$i$$$ 个字符描述第 $$$i$$$ 个灯的方向。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$100\,000$$$。
输出
对于每个测试用例,如果无法通过执行一项操作(或不执行任何操作)照亮所有奖杯,则打印 $$$-1$$$。否则,如果您选择不执行操作(即奖杯由灯的初始位置照亮),则打印 $$$0$$$;如果您选择交换灯 $$$i$$$ 和 $$$i+1$$$,则打印索引 $$$i$$$ ($$$1 \leq i < n$$$)。
如果有多个答案,请打印其中一个。
示例
输入 #1
6 2 LL 2 LR 2 RL 2 RR 7 LLRLLLR 7 RRLRRRL
输出 #1
-1 1 0 -1 3 6
注意
在第一个示例中,可以交换灯 $$$1$$$ 和 $$$2$$$,或者不执行任何操作。无论如何,都会获得字符串“LL”。并非所有奖杯都会被照亮,因为奖杯 $$$2$$$ 没有被任何灯照亮 - 灯 $$$1$$$ 不照亮任何东西,而灯 $$$2$$$ 仅照亮奖杯 $$$1$$$。
在第二个示例中,需要交换灯 $$$1$$$ 和 $$$2$$$。该字符串变为“RL”。奖杯$$$1$$$由灯$$$2$$$照亮,奖杯$$$2$$$由灯$$$1$$$照亮,因此可以照亮所有奖杯。
在第三个示例中,所有奖杯最初都会被照亮 - 因此,不执行任何操作是有效的解决方案。
在最后两个示例中,没有必要执行交换,因为所有奖杯最初都会被照亮。但是,所提出的解决方案也是有效的。