404514: GYM101522 F Frustrating Game

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Frustrating Gametime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The magician Alice is playing a game. Alice has N balls in a row, consists of red balls and blue balls. For convenience, the balls are numbered 1 to N from left to right. Her goal is to transform all balls into White by casting magic spells.

In a single spell, Alice can choose exactly R red balls and B blue balls at the same time, and then cast a spell on them, so all these R + B chosen balls will become white balls. However, there is a restriction: As some magical power may remains in the white balls, Alice cannot perform spells when there exists at least one white ball located between the leftmost chosen ball and the rightmost chosen ball.

For instance, if Alice balls 2, 6 and 7 have became white balls by previous spells, she cannot choose the set of balls {3, 8, 9} in a single spell as there exist a white ball numbered 5 between them. Similarly, single spell on balls {1, 3, 4}, {3, 4, 9} or {1, 9, 10} are invalid, while single spell on balls {3, 4, 5} or {8, 9, 10} are valid.

As Alice has spent more than hundred of years to achieve the goal and end up in failures, she is very frustrated. So, she promised that she will teach her magic skills to the one who can solve this frustrating game.

Nothing is more appealing than having an opportunity to learn magic! So you are trying to help Alice to achieve the goal.

Input

The first line contains 3 positive integers, N, R and B. (R, B ≥ 1, 1 ≤ R + B ≤ N ≤ 105)

The second line contains a string S, consisting of N characters R (red) and B (blue). The i-th character is the color of the i-th ball from the left.

Output

If it is impossible to achieve the goal, output NO on the first line.

Otherwise, output YES, followed by an integer S on the second line – the number of spells (S) you would like to cast.

In the next S lines, each should indicate a spell with R + B integers, representing the indices of the balls you have selected for this spell. You can output the indices in arbitrary order within the same line.

Please note that the spells should be printed in their chronological order. If there are more than one solution, you can output any of them.

ExamplesInput
6 1 1
BBRBRR
Output
YES
3
1 6
2 5
3 4
Input
8 1 2
RBRBRBRB
Output
NO
Input
10 2 3
BRRRBBBRBB
Output
YES
2
1 2 3 9 10
4 5 6 7 8
Note

In the first sample, the initial state is as follow:

After casting the first spell:

And after the second spell:

And the final state:

In the second sample, the initial state is as follow:

In the third sample, the initial state is as follow:

After casting the first spell:

And at last:

加入题单

上一题 下一题 算法标签: