Description

Little Edna has received the game Take-out as a present.

Take-out is a single-player game played on a sequence of $n$ adjacent blocks, numbered from $1$ to $n$. Each block is either white or black, and there are $k$ times as many white blocks as black blocks. The goal is to remove all blocks using permissible moves.

In a single move, you remove exactly $k$ white blocks and $1$ black block, without changing the positions of the other blocks. A move is permissible if there is no “gap” (a position of a previously removed block) between any two blocks removed in that move.

Find any sequence of permissible moves that removes all the blocks. It is guaranteed that a solution exists.

Input Format

In the first line of the standard input there are two integers, $n$ and $k$ ($2\le n\le 1\ 000\ 000$, $1\le k\le n-1$), separated by a single space, that denote the total number of blocks used in the game and the number of white blocks per black block (to be removed in every move). In all the tests the condition $k+1|n$ holds.

In the second line there is a string of $n$ letters 'b' or 'c'. These tell the colours of successive blocks (in Polish): 'b' (for biały) — white, 'c' (for czarny) — black. You may assume that in all the tests there exists a sequence of permissible moves that takes out all the blocks.

Output Format

Your program should print $\frac{n}{k+1}$ lines to the standard output. Successive lines should describe successive moves. Each line should contain $k+1$ integers, in increasing order, separated by single spaces, that denote the numbers of blocks to be removed in the move.

12 2
ccbcbbbbbbcb

1 8 12
2 6 7
3 4 5
9 10 11

Hint

Return TAT1: the same position is output $2$ times.

Return TAT2: among the $k+1$ output positions, the number of white blocks is not $k$ times the number of black blocks.

Return TAT3: the positions are not in increasing order, or the segment passes through a block that has already been removed.

SPJ provided by @colazcy.

Translated by ChatGPT 5