Write a backtracking program to print all the combinations of z zeros and o ones such that z + o = n, for a given n.

Input

Input consists of a natural number n > 0.

Output

Print all the combinations of z zeros and o ones such that z + o = n, one per line and in lexicographical order.

Observation

Although a backtracking program is not really necessary to solve this exercise, implement it anyway for the sake of practice.

Public test cases

**Input**

3

**Output**

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C C++ Haskell Java Python