← 返回题目列表

Codeforces · 1333/D

D. 学校的挑战第 41 号

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

有$$$n$$$个孩子,在41号学校学习。众所周知,他们是优秀的数学家。休息的时候,他们给自己安排了一次挑战。所有的孩子排成一排,头要么向左,要么向右。

孩子们可以执行以下操作:在一秒钟内,几对互相看着对方的相邻孩子可以同时将头转向相反的方向。例如,看着右边邻居的孩子会向左转,第二个孩子则相反。而且,每秒至少有一对相邻的孩子执行这样的动作。当附近没有一对互相看着对方的孩子时,他们就要结束了。

给你数字$$$n$$$、孩子的初始排列和数字$$$k$$$。如果孩子们想在 $$$k$$$ 秒内完成这个过程,你就必须找到一种让他们采取行动的方法。更正式地说,对于每一次 $$$k$$$ 移动,您需要输出在该移动过程中向左转的孩子的数量。

例如,对于如下所示的配置和 $$$k = 2$$$ 子级可以执行以下步骤:

保证如果解存在,则需要不超过$$$n^2$$$“头转向”。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 3000$$$, $$$1 \le k \le 3000000$$$) — 孩子的数量和所需的移动次数。

下一行包含长度为 $$$n$$$ 的字符串,仅包含字符 L 和 R,其中 L 表示子级向左看,R 表示子级向右看。

输出

如果没有解决方案,则打印一行,编号为$$$-1$$$。

否则,输出 $$$k$$$ 行。每行必须以数字 $$$n_i$$$ ($$$1\le n_i \le \frac{n}{2}$$$) 开头 - 在此移动中转动的孩子对的数量。之后打印 $$$n_i$$$ 不同的整数——在此移动过程中将向左转的孩子的数量。

完成所有“转头”后,不可能有两个相邻的孩子互相看着对方。

如果有很多解决方案,请打印其中任何一个。

示例

输入 #1

2 1
RL

输出 #1

1 1

输入 #2

2 1
LR

输出 #2

-1

输入 #3

4 2
RLRL

输出 #3

2 1 3 
1 2

注意

第一个样本包含一对互相看着对方的孩子。一步之后,他们就可以完成这个过程。

在第二个示例中,儿童无法进行任何移动。因此,它们不能以 $$$k>0$$$ 步数结束。

声明中描述了第三种配置。