Stuttering Strings

Interview

Time limit1sMemory limit128 MB

Summary

For each input case, the program prints every length-n string over * and ! whose runs stay within the given limits, in lexicographic order with * first.

Level: Easy3 of 10
Topics: Backtracking, Recursion, String
Solved: No attempts yet

Problem

We work with strings built from just two characters, * and !. For a fixed length we want to list every string that respects two run-length limits at the same time:

a string may contain at most nstar consecutive * characters, and
at most nbang consecutive ! characters.

Write a program that reads the length of the string together with the maximum allowed run of * and the maximum allowed run of !, then prints every acceptable string. The strings must be listed in lexicographic order, where * is treated as coming before !.

Input

The input is a sequence of lines. Each line holds three integers n, nstar, and nbang with $1 \le n \le 10$ . The input ends with a line that contains three zeros (0 0 0), which must not be processed.

Output

Number the input lines from 1 in the order they appear. For the k-th line first print a header line Sequence set k, then print, one per line, every string of length n that has no more than nstar consecutive * characters and no more than nbang consecutive ! characters. List the strings in lexicographic order with * before !. If no string qualifies for a case, print only its header line.

Examples3

Example 1

Input

Expected output

Sequence set 1
*
!
Sequence set 2
Sequence set 3
**
*!
!*

Example 2
Input
```
3 1 1
0 0 0
```
Expected output
```
Sequence set 1
*!*
!*!
```
Example 3
Input
```
2 1 1
0 0 0
```
Expected output
```
Sequence set 1
*!
!*
```