Without two consecutive ones#4835

Without two consecutive ones

1 second
128 megabytes
Very easy

Given positive integer , print all binary sequences of length without consecutive ones, in lexicographical order.

Input

One positive integer (n \le 20).

Output

Print each sequence in a separate line. Digits in a sequence must be separated with a space.

Examples

Example 1

Loading
Loading