Challenges in school №41
Contest: Codeforces Round 632 (Div. 2)
Difficulty rating: 2100
Tags: brute force, constructive algorithms, games, graphs, greedy, implementation, sortings

There are $$$n$$$ children, who study at the school №41. It is well-known that they are good mathematicians. Once at a break, they arranged a challenge for themselves. All children arranged in a row and turned heads either to the left or to the right.

Children can do the following: in one second several pairs of neighboring children who are looking at each other can simultaneously turn the head in the opposite direction. For instance, the one who was looking at the right neighbor turns left and vice versa for the second child. Moreover, every second at least one pair of neighboring children performs such action. They are going to finish when there is no pair of neighboring children who are looking at each other.

You are given the number $$$n$$$, the initial arrangement of children and the number $$$k$$$. You have to find a way for the children to act if they want to finish the process in exactly $$$k$$$ seconds. More formally, for each of the $$$k$$$ moves, you need to output the numbers of the children who turn left during this move.

For instance, for the configuration shown below and $$$k = 2$$$ children can do the following steps:

It is guaranteed that if the solution exists, it takes not more than $$$n^2$$$ "headturns".

Input format:
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 3000$$$, $$$1 \le k \le 3000000$$$)  — the number of children and required number of moves.

The next line contains a string of length $$$n$$$ and consists only of characters L and R, where L means that the child looks to the left and R means that the child looks to the right.

Output format:
If there is no solution, print a single line with number $$$-1$$$.

Otherwise, output $$$k$$$ lines. Each line has to start with a number $$$n_i$$$ ($$$1\le n_i \le \frac{n}{2}$$$)  — the number of pairs of children, who turn at this move. After that print $$$n_i$$$ distinct integers  — the numbers of the children who will turn left during this move.

After performing all "headturns", there can't be a pair of two neighboring children looking at each other.

If there are many solutions, print any of them.

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

Note:
The first sample contains a pair of children who look at each other. After one move, they can finish the process.

In the second sample, children can't make any move. As a result, they can't end in $$$k>0$$$ moves.

The third configuration is described in the statement.

Example input:
2 1
RL

Example output:
1 1

Example input:
2 1
LR

Example output:
-1

Editorial:
If solution exist let's count the minimum and maximum bounds for $$$k$$$ for initial arrangement of children. A minimum $$$k$$$ achieved all possible pairs of children turn theirs heads at every step. The maximum $$$k$$$ reached if only one of possible pairs of children turn theirs heads at every step. This values is easy to count, I'll leave it to you!
If $$$k$$$ from the statement not fit within our bounds, then we need to print $$$-1$$$. Otherwise solution exist and we need to construct them. For each next move we can use all pairs of children to turn theirs heads, decrease $$$k$$$ by 1 and recalculate maximum bound (lets call it $$$U$$$) on $$$k$$$ (just decrease them on the number of pairs used). If after moving new value of $$$k$$$ fits in the bound ($$$k \le U$$$), then we proceed to the next iteration. Otherwise, we roll back to the previous iteration and use $$$U - k + 1$$$ pairs in this move. Number of remaining moves will be $$$k - 1$$$ and upper bound will be $$$U - (U - k + 1) = k - 1$$$. And from that moment, just use only one pair in one move to the end of the process (to find one of the pair quickly we need to store them in the queue).
Final time complexity: $$$O(n^2)$$$