Before deciding going to CMU for graduate school, Cat was considering selling out and getting a real job out in industry. To do so, however, she had to pass the dreaded programming interviews. In one of her first interviews, she faced the following problem:

Given a length N and a count K, generate all the binary strings with exactly K 1's.  You will need to support binary strings of 1 <= N <= 16.

Being a noob at the time ¹, she failed and didn't pass the interview ². Her failure on this interview question haunts her to this day ³.

This is your opportunity to show that you are just as good as a CMU graduate student and solve this problem for Cat once and for all.

Input

You will be given a series of inputs where each line specifies N (length of binary string) and K (the number of 1s in the binary string):

Example Input

4 3
4 4

Output

For each pair of N and K inputs, print out all the binary strings with length N that contain exactly K 1s. If there is more than one binary string, then display them in lexigraphical order.

Note: Separate test cases by placing a blank line between them as shown below.

Example Output

0111
1011
1101
1110

1111

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa19-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge10               # Create and checkout challenge10 branch

$ $EDITOR challenge10/program.cpp           # Edit your code

$ git add challenge10/program.cpp           # Stage your changes
$ git commit -m "challenge10: done"         # Commit your changes

$ git push -u origin challenge10            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge10 assignment ...

Submitting challenge10 code ...
  Result Success
   Score 6.00
    Time 0.92

$ curl -F source=@challenge10/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa19/challenge10
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 05 TA List to determine your corresponding TA for the merge request.